Lovasova domněnka o Hamiltonově cyklu

Lovasova domněnka o Hamiltonově cyklu je klasickou domněnkou v teorii grafů.

Bylo formulováno ve čtvrtém díle Umění programování , ale s největší pravděpodobností bylo známo mnohem dříve.

Formulace

Každý konečně spojený vertex-tranzitivní graf obsahuje hamiltonovskou cestu .

Variace a zobecnění

Jakýkoli konečný připojený vertex-tranzitivní graf , kromě pěti výjimek, obsahuje Hamiltonův cyklus ; výjimky jsou:
- Kompletní graf , $K_{2}$
- Petersenův graf a graf z něj získaný nahrazením každého vrcholu trojúhelníkem,
- Coxeterův graf a graf z něj získaný nahrazením každého vrcholu trojúhelníkem.

Kompletní graf . $K_{2}$
hrabě Petersen.
hrabě z Coxeter.

Žádná z pěti výjimek není hrabě z Cayley . Toto pozorování vede ke slabší verzi hypotézy

Jakýkoli Cayleyův graf konečné grupy obsahuje Hamiltonův cyklus .

U řízených Cayleyových grafů není dohad pravdivý.

Speciální případy

Je známo, že orientovaný Cayleyův graf Abelovské grupy má hamiltonovskou cestu.
- Na druhé straně cyklické grupy, jejichž řád není mocninou prvočísla, připouštějí řízený Cayleyův graf bez Hamiltonova cyklu. [jeden]
V roce 1986 D. Witte dokázal, že domněnka platí pro Cayleyho grafy p-grup .
Tato otázka zůstává otevřená pro dihedrální skupiny .

Je známo, že pro symetrickou skupinu platí dohad pro následující sady generátorů:

$a=(1,2,\tečky ,n),b=(1,2)$ (dlouhý cyklus a transpozice ).
$s_{1}=(1,2),s_{2}=(2,3),\tečky ,s_{n-1}=(n-1,n)$ ( generátory Coxeter ). V tomto případě je Hamiltonův cyklus konstruován Steinhaus-Johnson-Trotterovým algoritmem .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Odkazy

↑ Holsztyński, W. & Strube, RFE (1978), Cesty a obvody v konečných grupách , Discrete Mathematics vol. 22 (3): 263–272 , DOI 10.1016/0012-365X(78)90059-6 .