Erdős-Gyárfásova domneva
Erdős-Gyárfásova domneva je v teoriji grafov nedokazana domneva, ki sta jo leta 1995 podala Paul Erdős in njegov sodelavec András Gyárfás. Domneva pravi, da vsak graf s stopnjo vsaj 3 vsebuje enostavni cikel, katerega dolžina je potenca 2. Erdős je za dokaz domneve ponudil 100 $ in 50 $ za protiprimer.

Z računalniškim iskanjem Gordona Roylea in Klasa Markströma je znano, da mora imeti protiprimer vsaj 17 točk, vsak protiprimer s kubičnim grafom pa vsaj 30 točk. Markström je z iskanjem našel štiri grafe na 24-ih točkah, v katerih ima edini cikel z dolžino potence 2 16 točk. Eden od teh grafov je ravninski in hkrati tudi Hamiltonov.

Delni rezultati 

Daniel in Shauger sta dokazala domnevo za ravninske grafe brez šap (brez zvezd s 3 povezavami). Shauger je dokazal domnevo tudi za -proste grafe z najmanjšo stopnjo vsaj  ali največjo stopnjo vsaj .

Sklici

Viri

Zunanje povezave 

 
 

Teorija grafov
Nerešeni matematični problemi
Paul Erdős
1995 v znanosti
Erdős - Gyárfásova domneva je v teoriji grafov nedokazana domneva , ki sta jo letapodala Paul Erdős in njegov sodelavec András Gyárfás . Domneva pravi , da vsak graf s stopnjo vsajvsebuje enostavni cikel , katerega dolžina je potenca Erdős je za dokaz domneve ponudil $ in $ za protiprimer . Z računalniškim iskanjem Gordona Roylea in Klasa Markströma je znano , da mora imeti protiprimer vsajtočk , vsak protiprimer s kubičnim grafom pa vsajtočk . Markström je z iskanjem našel štiri grafe naih točkah , v katerih ima edini cikel z dolžino potence16 točk . Eden od teh grafov je ravninski in hkrati tudi Hamiltonov . Delni rezultati Daniel in Shauger sta dokazala domnevo za ravninske grafe brez šap ( brez zvezd spovezavami ) . Shauger je dokazal domnevo tudi za - proste grafe z najmanjšo stopnjo vsaj ali največjo stopnjo vsaj \ . Sklici Viri Zunanje povezave Teorija grafov Nerešeni matematični problemi Paul Erdős 1995 v znanosti