A Lovász-sejtés a matematika, konkrétabban a gráfelmélet egyik nyitott kérdése. Így szól: Minden véges, összefüggő csúcstranzitív gráfban létezik Hamilton-út.
Lovász László eredetileg az állítást fordítva fogalmazta meg 1970-es cikkében, de a sejtés mégis a fenti megfogalmazásban terjedt el. Babai László 1996-ban publikált egy sejtést, ami erősen ellentmond a Lovász-sejtésnek, viszont egyelőre még mindkettő bizonyítatlan. Még az sem bizonyított, hogy egyetlen ellenpélda létezése ellenpéldák sokaságához vezetne-e.
Variációk Hamilton-kör biztosan nem létezik minden véges, összefüggő, csúcstranzitív gráfban. Öt ellenpélda ismert, nevezetesen a Petersen-gráf, a K2 teljes gráf, a Coxeter-gráf és két további gráf. Ezért a Hamilton-körös változat csak gyengítve fogalmazható meg:Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Az öt ismert kivételen kívül minden véges, összefüggő csúcstranzitív gráfban létezik Hamilton-kör. Az öt ismert ellenpélda közül egyik sem Cayley-gráf, ami szintén motivál egy változatot: Minden véges, összefüggő Cayley-gráf tartalmaz Hamilton-kört.
Ezeknek a változatoknak sincs általános, ismert bizonyítása.
A Cayley-gráfos változat kezelhető csoportelméleti módszerekkel és vannak is ismert eredmények speciális csoportok és generátorhalmazok esetében. Abel-csoportok és p-csoportok Cayley-gráfjaira például teljesül, de diédercsoportokra még mindig nincs eredmény.
Az szimmetrikus csoport esetén a sejtés teljesül ezekre a generátorhalmazokra:
(hosszú ciklus és egy transzpozíció) Coxeter-generátorok) a halmaz címkézett fáinak megfelelő transzpozíciók halmaza
Az irányított Cayley-gráfok esetén a sejtésre R.A. Rankin több ellenpéldát is adott.
Speciális esetek Abel-csoportok esetében az állítás elég egyszerűen belátható. Általános véges csoportokra csak néhány speciális generátorhalmaz esetében van bizonyítás: (Rankin-generátorok) (Rapaport-Strasser-generátorok) (Pak-Radoičić-generátorok) ahol (lásd: Glover-Marušič theorem)
Ismert továbbá az a tény, hogy minden véges csoporthoz létezik legfeljebb elemű generátorhalmaz úgy, hogy a hozzá tartozó Cayley-gráf tartalmaz Hamilton-kört (Pak-Radoičić). Ez az eredmény a véges egyszerű csoportok osztályozásán alapul.
Jegyzetek
Irodalom Babai László, Automorphism groups, isomorphism, reconstruction, Handbook of Combinatorics, Vol. 2, Elsevier, 1996, 1447-1540. Donald Knuth, A számítógép-programozás művészete, Vol. 4, draft of section 7.2.1.2. Igor Pak és Rados Radoičić, Hamiltonian paths in Cayley graphs, 2002.
Kategória:Gráfelmélet Kategória:Sejtések Kategória:Algebrai gráfelmélet Kategória:Hamilton-utak és -körök