Hypohamiltonsk graf

I grafteorien siges en graf G at være hypo -Hamiltonsk , hvis grafen i sig selv ikke har en Hamiltonsk cyklus , men enhver graf opnået ved at fjerne et toppunkt fra G er Hamiltonsk .

Historie

Hypo-Hamiltonske grafer blev første gang studeret af Sousselier i 1963 [2] . Lindgren [1] citerer Gaudin, Hertz og Rossi (1964) [3] , samt Busaker og Saaty (1965) [4] som yderligere materiale om dette emne. Et andet tidligt værk er et papir fra 1967 af Hertz, Duby og Vige [5] .

Grötschel [6] opsummerede det meste af arbejdet på dette område med følgende udsagn: "Aviser om disse grafer ... afslører normalt nye klasser af hypo-Hamiltonske og hypotegnede grafer og viser, at for nogle n eksisterer sådanne grafer, eller at de har mærkelige og uventede egenskaber."

Ansøgninger

Hypo-Hamiltonske grafer optræder i heltalsløsninger af problemet med den rejsende sælger - hypo-Hamiltonske grafer af en bestemt art definerer facetter af det rejsende sælger-polyhedron , en krop defineret som det konvekse skrog af sættet af mulige løsninger på problemet med den rejsende sælger, og disse facetter kan bruges til at skære plane metoder, når man løser problemet med Gomory-algoritmen [7] [6] [8] . Grötschel bemærkede [6] , at den beregningsmæssige kompleksitet ved at bestemme, om en graf er hypo-Hamiltonsk, selvom den ikke er kendt, synes at være høj, hvilket gør det vanskeligt at finde facetter af denne type, bortset fra facetter defineret af små hypo-Hamiltonske grafer . Heldigvis fører de mindste grafer til de stærkeste uligheder for et givet problem [9] .

Begreber svarende til hypo-Hamiltonianitet blev brugt af Park, Lim og Kim [10] til at måle fejltolerancen af ​​parallelle computernetværkstopologier .

Egenskaber

Enhver hypo-Hamiltonsk graf skal være vertex-3-connected , da fjernelse af to vilkårlige spidser efterlader en Hamiltonsk sti, der er forbundet (en graf med et vertex fjernet har en Hamiltonsk cyklus, og fjernelse af det andet knudepunkt giver en Hamiltonsk bane). Der er hypo-Hamiltonske grafer med n toppunkter, hvor den maksimale grad af et toppunkt er n /2 og hvor der er cirka n 2 /4 kanter [11] .

Hertz, Duby og Vige formodede [5] at enhver hypo-Hamiltonsk graf har omkreds 5 eller mere, men formodningen blev tilbagevist af Thomassen [12] , som fandt eksempler med omkreds 3 og 4. Det var ikke kendt i nogen tid, om hypo-Hamiltonske grafer kunne være plane , men nu kendes nogle eksempler på sådanne grafer [13] og den mindste af disse grafer har 40 hjørner [14] . Enhver plan hypo-Hamiltonsk graf har mindst ét ​​toppunkt med kun tre indfaldende kanter [15] .

Hvis en 3-homogen Hamiltonsk graf, kan dens kanter farves i tre farver - vi bruger skiftevis at farve kanterne med to farver langs Hamiltons cyklus (som skal have en lige længde ved håndtrykslemmaet ), og farve alle de resterende kanter med den tredje farve. Derfor skal alle snarks , kubiske broløse grafer, der kræver fire farver til kantfarvning, være ikke-hamiltonske, og mange kendte snarks er hypo-hamiltonske. Enhver hypocamiltonsk snark er bikritisk - sletning af to spidser efterlader en subgraf, hvis kanter kan farves i tre farver [16] [17] . Den tre-farvede farvning af denne undergraf kan let beskrives - efter fjernelse af toppunktet indeholder den resterende del en Hamiltonsk cyklus. Efter at have fjernet det andet toppunkt, bliver cyklussen en sti, hvis kanter skiftevis kan farves med to farver. De resterende kanter danner en matchende , og alle disse kanter kan farves med den tredje farve.

Farveklasserne for enhver 3-farvet kantfarvning af en 3-homogen graf danner tre matchninger, således at hver kant tilhører præcis én matchning. Hypo-Hamiltonske snarks har ikke en matchende nedbrydning af denne type, men Heggquist [18] formodede, at kanterne af enhver hypo-Hamiltonsk snark kan bruges til at danne seks matchninger, således at hver kant hører til præcis to matchninger. Dette er et særligt tilfælde af Berge-Fulkerson-formodningen om, at enhver snark har seks matchninger med denne egenskab.

Hypo-Hamiltonske grafer kan ikke være todelte – i en todelt graf kan et toppunkt kun fjernes for at danne en Hamiltonsk undergraf, hvis det tilhører den største af grafens to farveklasser. Imidlertid forekommer enhver todelt graf som en genereret undergraf af en hypo-Hamiltonsk graf [19] .

Eksempler

Den mindste hypo-Hamiltonske graf er Petersen-grafen [5] . Mere generelt er en generaliseret Petersen-graf GP( n ,2) hypo-Hamiltonsk, hvis n er 5 (mod 6) [20] . Petersen-grafen er en repræsentant for denne konstruktion med n  = 5.

Lindgren [1] fandt en anden uendelig klasse af hypo-Hamiltonske grafer, hvor antallet af hjørner er 4 (mod 6). Lindgrens konstruktion består af en cyklus med længde 3 (mod 6) og et centralt toppunkt. Det centrale toppunkt er forbundet med hvert tredje toppunkt i cyklussen med en kant, som han kalder en eger, og toppunkterne to positioner fra egens sidste toppunkt er forbundet med hinanden. Igen er den mindste repræsentant for Lindgren-konstruktionen Petersen-grafen.

Yderligere uendelige familier blev givet af Bondy [21] , Doyen og van Diest [22] og Gutt [23] .

Optælling

Vaclav Chvatal beviste i 1973, at for alle tilstrækkeligt store n er der hypo-Hamiltons med n toppunkter. Med efterfølgende opdagelser [24] [22] taget i betragtning , er "et tilstrækkeligt stort antal" nu kendt, så sådanne grafer eksisterer for alle n ≥ 18. En komplet liste over hypo-Hamiltonske grafer med højst 17 hjørner er kendt [ 25] - dette er Petersen-grafen med 10 toppunkter, grafer med 13 og 15 toppunkter fundet af Hertz ved hjælp af computersøgning [26] , og fire grafer med 16 toppunkter. Der er mindst tretten hypo-Hamiltonske grafer med 18 hjørner. Ved at anvende Chvatals triggermetode [27] på Petersen-grafen og blomstersnarken , kan det påvises, at antallet af hypo-Hamiltonske grafer, mere specifikt antallet af hypo-Hamiltonske snark, vokser som en eksponentiel for antallet af toppunkter [28] [29] .

Generaliseringer

Teoretikere studerer også hypotegnede grafer , grafer, der ikke indeholder en Hamiltonsk sti, men hvor en hvilken som helst delmængde af n  − 1 knudepunkter kan forbindes med en sti [30] [31] [32] [24] . Lignende definitioner af hypo-Hamiltonianitet og hypodrawability er blevet foreslået af nogle forfattere til rettede grafer [33] [34] [35] [15] .

En tilsvarende definition af hypo-Hamiltonske grafer er, at deres længste cyklusser er af længden n  − 1, og at skæringspunktet mellem alle længste cyklusser er tomt. Menke og Zamfirescu [36] studerede grafer med den egenskab, at skæringspunktet mellem de længste cyklusser er tomt, men hvor længden af ​​sådanne cyklusser er mindre end n  − 1. Hertz [26] definerede cyklerbarheden af ​​en graf som det største tal k sådan, at eventuelle k hjørner tilhører en cyklus. Hypo-Hamiltonske grafer er nøjagtigt grafer, der har cyklicitet n  − 1. På samme måde definerede Park, Lim og Kim [10] en graf til at være ƒ -stabilt ikke-Hamiltonsk, hvis fjernelse af højst ƒ hjørner giver en Hamiltonsk subgraf. Schauerte og Zamfirescu [37] studerede grafer med cyklicitet n  - 2.

Noter

  1. ↑ 1 2 3 Lindgren, 1967 .
  2. ↑ Sousselier, 1963 .
  3. ↑ Gaudin, Herz, Rossi, 1964 .
  4. ↑ Busacker, Saaty, 1965 .
  5. ↑ 1 2 3 Herz, Duby, Vigué, 1967 .
  6. ↑ 1 2 3 Grötschel, 1980 .
  7. ↑ Grotschel, 1977 .
  8. ↑ Grötschel, Wakabayashi, 1981 .
  9. ↑ Goemans, 1995 .
  10. ↑ 12 Park, Lim, Kim, 2007 .
  11. ↑ Thomassen, 1981 .
  12. ↑ Thomassen, 1974b .
  13. ↑ Problemet med eksistensen af ​​plane hypo-Hamiltonske grafer blev stillet som et åbent spørgsmål af Václav Chvátal ( Chvátal 1973 ), og en gruppe af Chvátal, Klarner og Knuth udlovede en præmie på $5 til finderen af ​​en sådan graf ( Chvátal, Klarner , Knuth 1972 ). Thomassen ( Thomasen 1976 ) brugte Greenbergs teorem til at finde plane hypo-Hamiltonske grafer med omkreds 3, 4 og 5 og viste, at der er uendeligt mange plane hypo-Hamiltonske grafer.
  14. ↑ Fundet af Juyande, McKay, Östergaard og Pettersson ( Jooyandeh, McKay, et al. 2013 ) ved hjælp af computersøgning og Greenbergs teorem. Forud for dette blev små plane hypo-Hamiltonske grafer med 42, 57 og 48 toppunkter fundet af Wiener og Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) og Zamfirescu (Zamfirescu, Zamfirescu 2007 ).
  15. ↑ 12 Thomassen , 1978 .
  16. ↑ Steffen, 1998 .
  17. ↑ Steffen, 2001 .
  18. ↑ Häggkvist, 2007 .
  19. ↑ Collier, Schmeichel, 1977 .
  20. ↑ Robertson ( 1969 ) beviste, at disse grafer er ikke-hamiltonske, selvom det let kan verificeres, at fjernelse af et toppunkt giver en Hamiltonsk graf. Se Alspachs papir ( Alspach 1983 ) om klassificeringen af ​​ikke-hamiltonske generaliserede Petersen-grafer.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Se også OEIS -sekvens A141150 .
  26. ↑ 12 Herz , 1968 .
  27. ↑ Chvatal, 1973 .
  28. ↑ Skupień, 1989 .
  29. ↑ Skupień, 2007 .
  30. ↑ Kapoor, Kronk, Lick, 1968 .
  31. ↑ Kronk, 1969 .
  32. ↑ Grünbaum, 1974 .
  33. ↑ Fouquet, Jolivet, 1978 .
  34. ↑ Grötschel, Wakabayashi, 1980 .
  35. ↑ Grötschel, Wakabayashi, 1984 .
  36. ↑ Menke, Zamfirescu, Zamfirescu, 1998 .
  37. ↑ Schauerte, Zamfirescu, 2006 .

Litteratur

Links