Conjectura lui Lovas despre ciclul hamiltonian

Conjectura lui Lovas despre ciclul hamiltonian este o presupunere clasică în teoria grafurilor.

A fost formulată în volumul al patrulea din The Art of Programming , dar cel mai probabil a fost cunoscut mult mai devreme.

Formulare

Fiecare graf tranzitiv-vertix conex finit conține o cale hamiltoniană .

Variații și generalizări

Orice graf conex finit vârf tranzitiv , cu excepția a cinci excepții, conține un ciclu hamiltonian ; excepțiile sunt:
- Graficul complet , $K_{2}$
- Graficul Petersen și graficul obținut din acesta prin înlocuirea fiecărui vârf cu un triunghi,
- Graficul Coxeter și graficul obținut din acesta prin înlocuirea fiecărui vârf cu un triunghi.

Graficul complet . $K_{2}$
Contele Petersen.
Contele de Coxeter.

Niciuna dintre cele cinci excepții nu este conte de Cayley . Această observație duce la o versiune mai slabă a ipotezei

Orice grafic Cayley al unui grup finit conține un ciclu hamiltonian .

Pentru graficele Cayley direcționate, conjectura nu este adevărată.

Cazuri speciale

Se știe că un grafic Cayley orientat al unui grup abelian are o cale hamiltoniană.
- Pe de altă parte, grupurile ciclice a căror ordine nu este o putere a unui prim admit un graf Cayley direcționat fără un ciclu hamiltonian. [unu]
În 1986, D. Witte a demonstrat că conjectura este adevărată pentru graficele Cayley ale grupurilor p .
Întrebarea rămâne deschisă pentru grupurile diedrice .

Se știe că pentru un grup simetric presupunerea este adevărată pentru următoarele seturi de generatoare:

$a=(1,2,\dots,n),b=(1,2)$ (ciclu lung și transpunere ).
$s_{1}=(1,2),s_{2}=(2,3),\dots ,s_{n-1}=(n-1,n)$ ( generatoare Coxeter ). În acest caz, ciclul hamiltonian este construit de algoritmul Steinhaus-Johnson-Trotter .
$a=(1,2),b=(1,2)(3,4)\cdots ,c=(2,3)(4,5)\cdots$ .

Link -uri

↑ 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 .