Hypohamiltonian graf

I grafteorin sägs en graf G vara hypo -Hamiltonsk , om grafen i sig inte har en Hamiltonsk cykel , men vilken graf som helst som erhålls genom att ta bort en vertex från G är Hamiltonsk .

Historik

Hypo-Hamiltonska grafer studerades först av Sousselier 1963 [2] . Lindgren [1] citerar Gaudin, Hertz och Rossi (1964) [3] , samt Busaker och Saaty (1965) [4] som ytterligare material om detta ämne. Ett annat tidigt arbete är ett papper från 1967 av Hertz, Duby och Vige [5] .

Grötschel [6] sammanfattade det mesta av arbetet inom detta område med följande uttalande: "Papper om dessa grafer ... avslöjar vanligtvis nya klasser av hypo-Hamiltoniska och hyporitade grafer och visar att för vissa n finns sådana grafer, eller att de har konstiga och oväntade egenskaper."

Applikationer

Hypo-Hamiltonska grafer förekommer i heltalslösningar av resandeförsäljarproblemet - hypo-Hamiltonska grafer av ett visst slag definierar aspekter av den resande försäljarens polyhedron , en kropp definierad som det konvexa skrovet av uppsättningen möjliga lösningar på resandeförsäljarproblemet, och dessa aspekter kan användas för att skära planmetoder när man löser problemet med Gomory-algoritmen [7] [6] [8] . Grötschel noterade [6] att beräkningskomplexiteten för att avgöra om en graf är hypo-Hamiltonsk, även om den inte är känd, verkar vara hög, vilket gör det svårt att hitta aspekter av denna typ, förutom fasetter som definieras av små hypo-Hamiltonska grafer . Lyckligtvis leder de minsta graferna till de starkaste ojämlikheterna för ett givet problem [9] .

Begrepp som liknar hypo-Hamiltonianitet användes av Park, Lim och Kim [10] för att mäta feltoleransen för parallella beräkningsnätverkstopologier .

Egenskaper

Varje hypo-Hamiltonsk graf måste vara vertex-3-connected , eftersom att ta bort två valfria hörn lämnar en Hamiltonsk bana som är ansluten (en graf med en vertex borttagen har en Hamiltonsk cykel, och att ta bort den andra vertexen ger en Hamiltonsk bana). Det finns hypo-Hamiltonska grafer med n hörn, där den maximala graden av en vertex är n /2 och där det finns ungefär n 2 /4 kanter [11] .

Hertz, Duby och Vige gissade [5] att varje hypo-Hamiltonsk graf har omkrets 5 eller mer, men gissningen motbevisades av Thomassen [12] , som hittade exempel med omkrets 3 och 4. Det var inte känt under en tid om huruvida hypo-Hamiltonska grafer skulle kunna vara plana , men nu är några exempel på sådana grafer kända [13] och den minsta av dessa grafer har 40 hörn [14] . Varje plan hypo-Hamiltonsk graf har minst en vertex med endast tre infallande kanter [15] .

Om en 3-homogen Hamiltonsk graf, kan dess kanter färgas i tre färger - vi använder växelvis färgning av kanterna med två färger längs Hamiltons cykel (som måste ha en jämn längd av handskakningslemma ), och färgar alla återstående kanter med den tredje färgen. Därför måste alla snarks , kubiska brygglösa grafer som kräver fyra färger för kantfärgning, vara icke-hamiltonska, och många kända snarks är hypo-hamiltonska. Varje hypocamiltonian snark är bikritisk - om två hörn tas bort lämnas en subgraf vars kanter kan färgas i tre färger [16] [17] . Den trefärgade färgningen av denna subgraf kan lätt beskrivas - efter att ha tagit bort vertexet innehåller den återstående delen en Hamiltonsk cykel. Efter att ha tagit bort den andra vertexen blir cykeln en bana vars kanter kan färgas omväxlande med två färger. De återstående kanterna bildar en matchande , och alla dessa kanter kan färgas med den tredje färgen.

Färgklasserna för varje 3-färgad kantfärgning av en 3-homogen graf bildar tre matchningar så att varje kant tillhör exakt en matchning. Hypo-Hamiltonska snarkar har inte en matchande nedbrytning av denna typ, men Heggquist [18] förmodade att kanterna på vilken hypo-Hamiltonsk snark som helst kan användas för att bilda sex matchningar så att varje kant tillhör exakt två matchningar. Detta är ett specialfall av Berge–Fulkersons gissning att varje snark har sex matchningar med den här egenskapen.

Hypo-Hamiltonska grafer kan inte vara tvådelade – i en tvådelad graf kan en vertex endast tas bort för att bilda en Hamiltonsk subgraf om den tillhör den största av grafens två färgklasser. Men vilken tvådelad graf som helst uppstår som en genererad subgraf till någon hypo-Hamiltonsk graf [19] .

Exempel

Den minsta hypo-Hamiltonska grafen är Petersen-grafen [5] . Mer allmänt är en generaliserad Petersen-graf GP( n ,2) hypo-Hamiltonisk om n är 5 (mod 6) [20] . Petersen-grafen är en representant för denna konstruktion med n  = 5.

Lindgren [1] hittade en annan oändlig klass av hypo-Hamiltonska grafer där antalet hörn är 4 (mod 6). Lindgrens konstruktion består av en cykel av längd 3 (mod 6) och en central vertex. Den centrala vertexen är ansluten till var tredje spets av cykeln med en kant, som han kallar en eker, och spetsarna två positioner från ekerns sista vertex är anslutna till varandra. Återigen är den minsta representanten för Lindgren-konstruktionen Petersen-grafen.

Ytterligare oändliga familjer gavs av Bondy [21] , Doyen och van Diest [22] och Gutt [23] .

Uppräkning

Vaclav Chvatal bevisade 1973 att för alla tillräckligt stora n finns hypo-Hamiltons med n hörn. Med efterföljande upptäckter [24] [22] beaktade , är "ett tillräckligt stort antal" nu känt, så att sådana grafer finns för alla n ≥ 18. En fullständig lista över hypo-Hamiltonska grafer med högst 17 hörn är känd [ 25] - detta är Petersen-grafen med 10 hörn, grafer med 13 och 15 hörn hittade av Hertz med hjälp av datorsökning [26] , och fyra grafer med 16 hörn. Det finns minst tretton hypo-Hamiltonska grafer med 18 hörn. Genom att tillämpa Chvatals triggermetod [27] på Petersen-grafen och blomsnarken , kan det visas att antalet hypo-Hamiltonska grafer, närmare bestämt antalet hypo-Hamiltonska snark, växer som en exponential av antalet hörn [28] [29] .

Generaliseringar

Teoretiker studerar också hyporitade grafer , grafer som inte innehåller en Hamiltonsk väg, men där vilken delmängd som helst av n  − 1 hörn kan kopplas samman med en väg [30] [31] [32] [24] . Liknande definitioner av hypo-Hamiltonianitet och hypodrawability har föreslagits av vissa författare för riktade grafer [33] [34] [35] [15] .

En ekvivalent definition av hypo-Hamiltonska grafer är att deras längsta cykler är av längden n  − 1 och att skärningspunkten för alla längsta cykler är tom. Menke och Zamfirescu [36] studerade grafer med egenskapen att skärningspunkten för de längsta cyklerna är tom, men där längden på sådana cykler är mindre än n  − 1. Hertz [26] definierade cyklerbarheten för en graf som det största antalet k så att alla k hörn hör till en cykel. Hypo-Hamiltonska grafer är exakt grafer som har cyklicitet n  − 1. På liknande sätt definierade Park, Lim och Kim [10] en graf till att vara ƒ -stabilt icke-Hamiltonsk om man tar bort högst ƒ hörn ger en Hamiltonsk subgraf. Schauerte och Zamfirescu [37] studerade grafer med cyklicitet n  - 2.

Anteckningar

  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 förekomsten av plana hypo-Hamiltonska grafer ställdes som en öppen fråga av Václav Chvátal ( Chvátal 1973 ) och en grupp av Chvátal, Klarner och Knuth utlovade ett pris på $5 till upptäckaren av en sådan graf ( Chvátal, Klarner Knuth 1972 ). Thomassen ( Thomassen 1976 ) använde Greenbergs teorem för att hitta plana hypo-Hamiltonska grafer med omkrets 3, 4 och 5 och visade att det finns oändligt många plana hypo-Hamiltonska grafer.
  14. ↑ Funnet av Juyande, McKay, Östergaard och Pettersson ( Jooyandeh, McKay, et al. 2013 ) med hjälp av datorsökning och Greenbergs teorem. Dessförinnan har små plana hypo-Hamiltonska grafer med 42, 57 och 48 hörn hittats av Wiener och Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) och 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 ) bevisade att dessa grafer är icke-hamiltonska, även om det lätt kan verifieras att om man tar bort en vertex får man en hamiltonsk graf. Se Alspachs artikel ( Alspach 1983 ) om klassificeringen av icke-hamiltonska generaliserade Petersen-grafer.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Se även 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

Länkar