Szub-Hamilton gráf

A szub- Hamilton-gráf egy síkbeli Hamilton-gráf részgráfja [1] [2] .

Definíció

Egy G gráf szub-Hamilton-féle, ha G egy másik aug( G ) gráf részgráfja, amelynek ugyanaz a csúcskészlete, míg az aug( G ) gráf síkbeli és egy Hamilton-ciklust tartalmaz . Ahhoz, hogy ezek a feltételek teljesüljenek, magának a G gráfnak síknak kell lennie, és ezen felül lehetővé kell tenni síkosság-megőrző élek hozzáadását, hogy olyan ciklust hozzunk létre a kiterjesztett gráfban, amely az összes csúcsot pontosan egyszer bejárja. Az aug( G ) gráfot a G gráf Hamilton kiterjesztésének nevezzük [2] .

Egy szub-Hamilton-gráfot egy Hamilton-gráf részgráfjaként definiálhatunk anélkül, hogy a nagyobb gráfnak ugyanazzal a csúcskészlettel kell rendelkeznie. Vagyis ebben az alternatív definícióban csúcsok és élek adhatók hozzá. Ha azonban egy gráf csúcsok és élek hozzáadásával Hamilton-félevé tehető, akkor csúcsok hozzáadása nélkül is Hamilton-félevé tehető, így ez a többletszabadság nem változtat a definíción [3]

Egy szub-Hamilton-gráfban a szub-Hamilton-ciklus csúcsok ciklikus sorozata, így a sorozat bármely csúcspárjához él hozzáadása nem töri meg a gráf síkságát. Egy gráf akkor és csak akkor szub-Hamilton-féle, ha van Hamilton alatti ciklusa [4] .

Előzmények és alkalmazások

A Hamilton alatti gráfok osztályát (de nem az osztály nevét) Bernhart és Kainen javasolta [5] . Bebizonyították, hogy pontosan ezek a grafikonok, amelyeknek két oldala van a könyvmellékletekben [6] . Szub-Hamilton-gráfokat és Hamilton-kiterjesztéseket is alkalmaztak a gráfvizualizáció területén a gráfok univerzális ponthalmazba történő beágyazásának , több gráf egyidejű beágyazásának és a gráf rétegenkénti rajzolásának problémáira [2] .

Kapcsolódó grafikoncsaládok

A síkgráfok bizonyos osztályai szükségszerűen Hamilton-féle, tehát szub-Hamilton-féleek. Ide tartoznak a 4 csúcshoz kapcsolódó gráfok [7] és a Halin-gráfok [8] .

Minden olyan síkgráf, amelynek maximális foka nem haladja meg a négyet, szub-Hamilton-féle [4] , akárcsak minden elválasztó háromszög nélküli síkgráf [9] [10] . Ha egy tetszőleges síkgráf éleit kettes hosszúságú pályákra bontjuk [11] , az eredményül kapott gráf mindig Hamilton alatti [2] .

Jegyzetek

  1. ↑ Heath, 1987 , p. 198–218.
  2. ↑ 1 2 3 4 Di Giacomo, Liotta, 2010 , p. 35–46.
  3. ↑ Például a "Grafikok könyvbeágyazásai és Whitney tétele, 2017. augusztus 29-én archivált a Wayback Machine -nél " című 2003-as tanulmányában Paul Kainen a szub-Hamilton-gráfokat síkbeli Hamilton-gráfok részgráfjaiként határozza meg, anélkül, hogy korlátozná a csúcspontot. kiterjesztett gráf, de azt írja, hogy "egy Hamilton alatti gráf definíciójában megkövetelhető, hogy a bővítést csak élek hozzáadásával végezzük"
  4. ↑ 1 2 Bekos, Gronemann, Raftopoulou, 2014 .
  5. ↑ Bernhart, Kainen, 1979 .
  6. ↑ Bernhart és Kainen 1979 , p. 320–331.
  7. ↑ Nishizeki, Chiba, 2008 , p. 171–184.
  8. ↑ Cornuéjols, Naddef, Pulleyblank, 1983 , p. 287–294.
  9. ↑ Kainen, Overbay, 2007 , p. 835–837.
  10. ↑ Az elválasztó háromszög egy három csúcsot és három élt tartalmazó részgráf, amelynek eltávolítása (a szomszédos élekkel együtt) a gráf szétválasztott részekre való felosztásához vezet ( Duncan, Goodrich, Kobourov 2003 ).
  11. ↑ Ez azt jelenti, hogy minden él két élré alakul, ha egy csúcsot helyezünk az élre.

Irodalom