Prehodnost v točkovno tranzitivnih grafih
natisniAli ima vsak povezan točkovno tranzitiven graf (graf X, katerega grupa avtomorfizmov Aut(X) deluje tranzitivno na množici točk V(X) ali TTG na kratko) hamiltonsko pot (enostavno pot, ki vsebuje vse točke grafa)?
Protiprimera za zapisano domnevo ne poznamo. Poleg tega so izmed vseh znanih povezanih točkovno tranzitivnih grafov znani le štirje grafi na vsaj treh točkah, ki nimajo hamiltonskega cikla - enostavenega cikla, ki vsebuje vse točke grafa. Dejstvo, da noben izmed teh štirih grafov ni Cayleyev (t.j. TTG, katerega grupa avtomorfizmov premore regularno podgrupo (Cayleyevo grupo)), je pripeljalo do splošne domneve, da ima vsak povezan Cayleyev graf hamiltonski cikel.
V projektu bo problem obstoja hamiltonskih poti in ciklov v povezanih TTG-ih poimenovan HPC problem. Ta problem je bil/je eden izmed glavnih katalizatorjev razvoja algebraične teorije grafov, ki je ena od najhitreje rastočih raziskovalnih področij v diskretni matematiki. Kubični TTG imajo osrednji položaj v trenutnih raziskavah tega problema, in sicer zaradi očitnega razloga: pomanjkanje povezav intuitivno otežuje iskanje poti ali ciklov, kar podpira dejstvo, da so vsi znani TTG brez hamiltonskih ciklov kubični.
Cilj projekta je narediti pomemben prispevek v smeri popolne rešitve HPC problema, s posebnim poudarkom na Cayleyevih grafih.
