Lovas' formodning om Hamiltons cyklus

Lovas' formodning om Hamiltons cyklus er en klassisk formodning inden for grafteori.

Det blev formuleret i fjerde bind af The Art of Programming , men højst sandsynligt var det kendt meget tidligere.

Ordlyd

Hver endeligt forbundet vertex-transitiv graf indeholder en Hamilton-sti .

Variationer og generaliseringer

Enhver finit forbundet vertex-transitiv graf , bortset fra fem undtagelser, indeholder en Hamilton-cyklus ; undtagelser er:
- Komplet graf , $K_{2}$
- Petersen- grafen og grafen opnået fra den ved at erstatte hvert toppunkt med en trekant,
- Coxeter- grafen og grafen opnået fra den ved at erstatte hvert hjørne med en trekant.

Komplet graf . $K_{2}$
grev Petersen.
Jarl af Coxeter.

Ingen af de fem undtagelser er en Earl of Cayley . Denne observation fører til en svagere version af hypotesen

Enhver Cayley-graf for en endelig gruppe indeholder en Hamilton-cyklus .

For rettede Cayley-grafer er formodningen ikke sand.

Særlige tilfælde

Det er kendt, at en orienteret Cayley-graf af en Abelsk gruppe har en Hamiltonsk sti.
- På den anden side indrømmer cykliske grupper, hvis rækkefølge ikke er en potens af et primtal, en rettet Cayley-graf uden en Hamiltonsk cyklus. [en]
I 1986 beviste D. Witte, at formodningen er sand for Cayley-graferne for p-grupper .
Spørgsmålet forbliver åbent for dihedrale grupper .

Det er kendt, at for en symmetrisk gruppe er formodningen sand for følgende sæt af generatorer:

$a=(1,2,\dots ,n),b=(1,2)$ (lang cyklus og transponering ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( Coxeter generatorer ). I dette tilfælde er den Hamiltonske cyklus konstrueret af Steinhaus-Johnson-Trotter-algoritmen .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Links

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