Hypohamiltonský graf

V teorii grafů se o grafu G říká, že je hypo -hamiltonovský , pokud graf sám o sobě nemá hamiltonovský cyklus , ale jakýkoli graf získaný odstraněním jednoho vrcholu z G je hamiltonovský .

Historie

Hypo-Hamiltonovské grafy byly poprvé studovány Sousselierem v roce 1963 [2] . Lindgren [1] cituje Gaudina, Hertze a Rossiho (1964) [3] , jakož i Busakera a Saatyho (1965) [4] jako další materiál na toto téma. Další ranou prací je článek Hertze, Dubyho a Vige z roku 1967 [5] .

Grötschel [6] shrnul většinu práce v této oblasti následujícím prohlášením: „Články o těchto grafech... obvykle odhalují nové třídy hypo-hamiltonských a hypokreslených grafů a ukazují, že pro některé n takové grafy existují, resp. mají zvláštní a nečekané vlastnosti."

Aplikace

Hypohamiltonské grafy se objevují v celočíselných řešeních problému obchodního cestujícího - hypohamiltonské grafy určitého druhu definují aspekty mnohostěnu obchodního cestujícího , tělesa definovaného jako konvexní obal množiny možných řešení problému obchodního cestujícího, a tyto fasety lze použít pro metody řezné roviny při řešení problému s Gomoryho algoritmem [7] [6] [8] . Grötschel poznamenal [6] , že výpočetní složitost určení, zda je graf hypo-hamiltonovský, i když není známa, se zdá být vysoká, takže je obtížné najít aspekty tohoto typu, s výjimkou aspektů definovaných hypo-hamiltonskými grafy malé velikosti. . Naštěstí nejmenší grafy vedou k nejsilnějším nerovnostem pro daný problém [9] .

Koncepty podobné hypo-hamiltonianitě byly použity Parkem, Limem a Kimem [10] k měření chybové odolnosti topologií paralelních počítačových sítí .

Vlastnosti

Jakýkoli hypo-hamiltonovský graf musí být vertex-3-connected , protože odstranění jakýchkoli dvou vrcholů zanechá hamiltonovskou cestu, která je spojena (graf s odstraněným jedním vrcholem má hamiltonovský cyklus a odstraněním druhého vrcholu vznikne hamiltonovská cesta). Existují hypohamiltonovské grafy s n vrcholy, ve kterých je maximální stupeň vrcholu n /2 a ve kterých je přibližně n 2 /4 hran [11] .

Hertz, Duby a Vige se domnívali [5] , že jakýkoli hypo-hamiltonovský graf má obvod 5 nebo více, ale domněnku vyvrátil Thomassen [12] , který našel příklady s obvodem 3 a 4. Nějakou dobu nebylo známo, zda hypo-hamiltonské grafy mohou být rovinné , ale nyní jsou známy některé příklady takových grafů [13] a nejmenší z těchto grafů má 40 vrcholů [14] . Každý rovinný hypo-hamiltonovský graf má alespoň jeden vrchol pouze se třemi dopadajícími hranami [15] .

Jde- li o 3-homogenní hamiltonovský graf, mohou být jeho hrany obarveny třemi barvami - používáme střídavě obarvování hran dvěma barvami podél hamiltonovského cyklu (který musí mít podle lemmatu handshake sudou délku ) a všechny zbývající hrany obarvíme třetí barva. Tudíž všechny snarks , kubické bezmůstkové grafy vyžadující čtyři barvy pro zbarvení hran, musí být nehamiltonovské a mnoho známých snarků je hypo-hamiltonských. Nějaký hypocamiltonian snark je bikritický — vymazání nějakých dvou vertices zanechá podgraf jehož okraje mohou být obarveny ve třech barvách [16] [17] . Tříbarevné zbarvení tohoto podgrafu lze jednoduše popsat - po odstranění vrcholu obsahuje zbývající část Hamiltonovský cyklus. Po odstranění druhého vrcholu se z cyklu stane cesta, jejíž okraje lze střídavě obarvit dvěma barvami. Zbývající okraje tvoří odpovídající a všechny tyto okraje lze obarvit třetí barvou.

Barevné třídy jakéhokoli 3-barevného obarvení hran 3-homogenního grafu tvoří tři shody tak, že každá hrana patří přesně jedné shodě. Hypo-hamiltonští snarkové nemají odpovídající rozklad tohoto typu, ale Heggquist [18] se domníval, že hrany jakéhokoli hypo-hamiltonského snark mohou být použity k vytvoření šesti shod tak, že každá hrana patří přesně dvěma shodám. Toto je zvláštní případ Berge-Fulkersonovy domněnky, že každý snark má šest shod s touto vlastností.

Hypo-hamiltonské grafy nemohou být bipartitní – v bipartitním grafu lze vrchol odstranit a vytvořit tak hamiltonovský podgraf pouze tehdy, pokud patří do větší ze dvou barevných tříd grafu. Každý bipartitní graf se však vyskytuje jako generovaný podgraf nějakého hypo-hamiltonovského grafu [19] .

Příklady

Nejmenším hypohamiltonovským grafem je Petersenův graf [5] . Obecněji je zobecněný Petersenův graf GP( n ,2) hypo-hamiltonovský, jestliže n je 5 (mod 6) [20] . Petersenův graf je zástupcem této konstrukce s n  = 5.

Lindgren [1] našel další nekonečnou třídu hypo-Hamiltonových grafů, ve kterých je počet vrcholů 4 (mod 6). Lindgrenova konstrukce se skládá z cyklu délky 3 (mod 6) a jednoho centrálního vrcholu. Centrální vrchol je spojen s každým třetím vrcholem cyklu hranou, kterou nazývá paprskem, a vrcholy dvě pozice od konečného vrcholu paprsku jsou navzájem spojeny. Opět nejmenším zástupcem Lindgrenovy konstrukce je Petersenův graf.

Další nekonečné rodiny uvedli Bondy [21] , Doyen a van Diest [22] a Gutt [23] .

Výčet

Václav Chvátal v roce 1973 dokázal, že pro všechna dostatečně velká n existují hypo-Hamiltony s n vrcholy. S přihlédnutím k následným objevům [24] [22] je nyní známo "dostatečně velké číslo", takže takové grafy existují pro všechna n ≥ 18. Je znám úplný seznam hypo-hamiltonských grafů s nejvýše 17 vrcholy [ 25] - toto je Petersenův graf s 10 vrcholy, grafy s 13 a 15 vrcholy nalezenými Hertzem pomocí počítačového vyhledávání [26] a čtyři grafy s 16 vrcholy. Existuje nejméně třináct hypo-hamiltonských grafů s 18 vrcholy. Aplikací Chvatalovy spouštěcí metody [27] na Petersenův graf a květinový snark lze ukázat, že počet hypohamiltonských grafů, konkrétněji počet hypohamiltonských snarků, roste jako exponenciála počtu vrcholů. [28] [29] .

Zobecnění

Teoretici také studují hypodrawn grafy , grafy, které neobsahují hamiltonovskou cestu, ale ve kterých může být jakákoli podmnožina n  − 1 vrcholů spojena cestou [30] [31] [32] [24] . Podobné definice hypo-hamiltonianity a hypodrawability byly navrženy některými autory pro orientované grafy [33] [34] [35] [15] .

Ekvivalentní definice hypohamiltonských grafů je, že jejich nejdelší cykly mají délku n  − 1 a že průsečík všech nejdelších cyklů je prázdný. Menke a Zamfirescu [36] studovali grafy s vlastností, že průsečík nejdelších cyklů je prázdný, ale délka takových cyklů je menší než n  − 1. Hertz [26] definoval cyklovatelnost grafu jako největší číslo. k takové, že všech k vrcholů patří do cyklu. Hypo-hamiltonské grafy jsou přesně grafy, které mají cykličnost n  − 1. Podobně Park, Lim a Kim [10] definovali graf jako ƒ - stabilně nehamiltonovský, pokud odstraněním nejvýše ƒ vrcholů vznikne hamiltonovský podgraf. Schauerte a Zamfirescu [37] studovali grafy s cykličností n  − 2.

Poznámky

  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. ↑ Problém existence planárních hypohamiltonských grafů položil jako otevřenou otázku Václav Chvátal ( Chvátal 1973 ) a skupina Chvátal, Klarner a Knuth přislíbila nálezci takového grafu odměnu 5 dolarů ( Chvátal, Klarner Knuth, 1972 ). Thomassen ( Thomassen 1976 ) použil Greenbergovu větu k nalezení rovinných hypo-Hamiltonovských grafů s obvodem 3, 4 a 5 a ukázal, že existuje nekonečně mnoho rovinných hypo-Hamiltonovských grafů.
  14. ↑ Nalezli Juyande, McKay, Östergaard a Pettersson ( Jooyandeh, McKay, et al. 2013 ) pomocí počítačového vyhledávání a Greenbergova teorému. Předtím nalezli Wiener a Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) a Zamfirescu (Zamfirescu, Zamfirescu 2007 ) malé planární hypohamiltonovské grafy se 42, 57 a 48 vrcholy.
  15. ↑ 12 Thomassen , 1978 .
  16. ↑ Steffen, 1998 .
  17. ↑ Steffen, 2001 .
  18. ↑ Häggkvist, 2007 .
  19. ↑ Collier, Schmeichel, 1977 .
  20. ↑ Robertson ( 1969 ) dokázal, že tyto grafy jsou nehamiltonovské, i když lze snadno ověřit, že odstraněním jednoho vrcholu vznikne hamiltonovský graf. Viz Alspachův článek ( Alspach 1983 ) o klasifikaci nehamiltonovských zobecněných Petersenových grafů.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Viz také OEIS sekvence A141150 .
  26. ↑ 12 Herz , 1968 .
  27. ↑ Chvátal, 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 .

Literatura

Odkazy