|
Opis
Description
|
Motivacija za predlagani projekt, ki obravnava simetrije hamiltonskih ciklov v povezanih točkovno tranzitivnih grafih, izhaja iz nedavno vpeljane 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 enakom 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 rotac 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č 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 ka 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. |
|
Sodelujoče organizacije
Participating organizations
|
InnoRenew CoE (Michael Mrissa, Balazs David); Univerza v Ljubljani, Pedagoška fakulteta (Primož Šparl, Dragan Marušič, Aleksander Malnič); razsikovalni skupini iz University of Lethbridge, Kanada (vodja Dave Witte Morris) in Capital Normal University, Kitajska (vodja Shaofei Du) |
