Lovas sejtése a Hamilton-ciklusról

Lovasnak a Hamilton-ciklusról szóló sejtése a gráfelmélet klasszikus sejtése.

A programozás művészete negyedik kötetében fogalmazódott meg , de nagy valószínűséggel jóval korábban ismerték.

Megfogalmazás

Minden véges összefüggő csúcstranzitív gráf tartalmaz egy Hamilton-pályát .

Változatok és általánosítások

Bármely véges összefüggő csúcstranzitív gráf öt kivételtől eltekintve tartalmaz egy Hamilton-ciklust ; kivételek a következők:
- Teljes grafikon , $K_{2}$
- A Petersen -gráf és a belőle kapott gráf, ha minden csúcsot háromszöggel helyettesítünk,
- A Coxeter -gráf és a belőle kapott gráf minden csúcsnak egy háromszöggel való helyettesítésével.

Teljes grafikon . $K_{2}$
Petersen gróf.
Coxeter grófja.

Az öt kivétel egyike sem Cayley grófja . Ez a megfigyelés a hipotézis gyengébb változatához vezet

Egy véges csoport bármely Cayley-gráfja tartalmaz egy Hamilton-ciklust .

Irányított Cayley-gráfok esetében a sejtés nem igaz.

Különleges esetek

Ismeretes, hogy egy Abel-csoport orientált Cayley-gráfjának Hamilton-útvonala van.
- Másrészt azok a ciklikus csoportok, amelyek sorrendje nem egy prím hatványa, beengednek egy irányított Cayley-gráfot Hamilton-ciklus nélkül. [egy]
1986-ban D. Witte bebizonyította, hogy a sejtés igaz a p-csoportok Cayley-gráfjaira .
A kérdés nyitott marad a diédercsoportok számára .

Ismeretes, hogy egy szimmetrikus csoportra a sejtés igaz a következő generátorkészletekre:

$a=(1,2,\pontok ,n),b=(1,2)$ (hosszú ciklus és átültetés ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( Coxeter generátorok ). Ebben az esetben a Hamilton-ciklust a Steinhaus-Johnson-Trotter algoritmus alkotja meg .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Linkek

↑ Holsztyński, W. & Strube, RFE (1978), Útvonalak és áramkörök véges csoportokban , Discrete Mathematics 22. kötet (3): 263–272 , DOI 10.1016/0012-365X(78)90059-6 .