Hamiltonski cikli z rotacijsko simetrijo v povezanih točkovno tranzitivnih grafih

Motivacija za predlagani projekt, ki obravnava simetrije hamiltonskih ciklov v povezanih točkovno tranzitivnih grafih, izhaja iz nedavno vpeljanega parametra grafa, ki kvantificira, kako simetričen je lahko Hamiltonov cikel v grafu. Parameter so leta 2022 definirali Gregor, Merino in Muetze. Formalno, naj bo X graf z n točkami. Pravimo, da je hamiltonski cikel C=(v0,...,vn-1) is k-simetričen, če je preslikava f :V(X) ->V(X) definirana z f(vi)=vi+n/k za vse i=0,...,n-1, kjer so indeksi obravnavani po modulu n, avtomorfizem grafa X. V tem primeru imamo C=(P,f (P), f 2(P),...,f k-1(P)) za pot P=v0,...,vn/k-1. Z večkratno uporabo avtomorfizma f, je torej mogoče cikel C rekonstruirati s pomočjo poti P, ki vsebuje zgolj 1/k točk. Če točke grafa enakomerno razporedimo na krog v ravnini in narišemo povezave grafa X z ravnimi daljicami, potem dobimo prikaz (risbo) grafa X v ravnini s k-kratno rotacijsko simetrijo. V taki predstavnitvi grafa X je torej f rotacija za 360/k stopinj. Največje število k, za katerega je hamiltonski cikel C grafa X k-simetričen, se imenuje kompresijski faktor cikla of C, označujemo pa ga s kappa(X,C). Za graf X definiramo kappa(X)=max{kappa(X,C) | C je hamiltonski cikel grafa X}, in ta parameter imenujemo hamiltonska kompresija grafa X. Če graf X nima hamiltonskega cikla, potem definiramo kappa(X)=0. Parameter kappa(X) lahko torej razumemo kot merilo za najlepši (to je najbolj simetričen) prikaz grafa X na krogu v ravnini. Glavni cilj predlaganega projekta je študij hamiltonske kompresije povezanih točkovno tranzitivnih grafov, tako tistih, za katere vemo, da imajo hamiltonske cikle, kakor tudi, glede na povezavo s policirkulantno domnevo, za tiste grafe, za katere še nimamo informacij o obstoju hamiltonskih ciklov. V tem smislu se predlagani projekt navezuje tudi na Lovaszov problem hamiltonskosti točkovno tranzitivnih grafov.