Lovas gissningar om Hamiltons cykel

Lovas gissning om Hamiltons cykel är en klassisk gissning inom grafteorin.

Det formulerades i fjärde volymen av Konsten att programmera , men troligen var det känt mycket tidigare.

Formulering

Varje finit ansluten vertextransitiv graf innehåller en Hamiltonsk väg .

Variationer och generaliseringar

Varje finit ansluten vertextransitiv graf , med undantag för fem undantag, innehåller en Hamiltonsk cykel ; undantag är:
- Komplett graf , $K_{2}$
- Petersen -grafen och grafen som erhålls från den genom att ersätta varje vertex med en triangel,
- Coxeter- grafen och grafen som erhålls från den genom att ersätta varje vertex med en triangel.

Komplett graf . $K_{2}$
Greve Petersen.
Earl av Coxeter.

Inget av de fem undantagen är en Earl of Cayley . Denna observation leder till en svagare version av hypotesen

Varje Cayley-graf för en ändlig grupp innehåller en Hamiltonsk cykel .

För riktade Cayley-grafer är gissningen inte sann.

Specialfall

Det är känt att en orienterad Cayley-graf för en Abelisk grupp har en Hamiltonsk väg.
- Å andra sidan erkänner cykliska grupper vars ordning inte är en primtalspotens en riktad Cayley-graf utan en Hamiltonsk cykel. [ett]
1986 bevisade D. Witte att gissningen är sann för Cayley-graferna för p-grupper .
Frågan är fortfarande öppen för dihedriska grupper .

Det är känt att för en symmetrisk grupp är gissningen sann för följande uppsättningar av generatorer:

$a=(1,2,\dots ,n),b=(1,2)$ (lång cykel och införlivande ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( Coxeter-generatorer ). I det här fallet är den Hamiltonska cykeln konstruerad av Steinhaus-Johnson-Trotter-algoritmen .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Länkar

↑ Holsztyński, W. & Strube, RFE (1978), Paths and circuits in finite groups , Discrete Mathematics vol. 22 (3): 263–272 , DOI 10.1016/0012-365X(78)90059-6 .