Temeljni projekt J1-50000
Hamiltonski cikli z rotacijsko simetrijo v povezanih točkovno tranzitivnih grafih

 

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

Vodja projekta: Dragan Marušič

Šifra projekta: J1-50000.

Tip projekta: temeljni projekt.

Financer: Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost RS (ARIS).

Raziskovalno področje (ARRS): 1.01.00 - Naravoslovno-matematične vede / Matematika.

Trajanje projekta: 1. 10. 2023 - 30. 9. 2026.

Cenovna kategorija projekta: B.

Letni obseg projekta: 1.35 FTE (2.294 raziskovalnih ur).

Sicris profil projekta je dostopen tukaj.

Raziskovalne organizacije v okviru katerih se izvaja projekt:

Univerza na Primorskem, Inštitut Andrej Marušič
Univerza v Ljubljani, Pedagoška fakulteta
InnoRenew CoE

Člani raziskovalnega projekta:

Dragan Marušič (ARIS šifra 02887)

Istvan Kovacs (ARIS šifra 25997)

Klavdija Kutnar (ARIS šifra 24997)

Edward Tauscher Dobson (ARIS šifra 34109)

Russell Stephen Woodroofe (ARIS šifra 50355)

Štefko Miklavič (ARIS šifra 21656)

Ademir Hujdurović (ARIS šifra 32518)

Sarobidy Razafimahatratra Andriaherimanana (ARIS šifra 56940)

Blas Fernandez (ARIS šifra 52892)

Draženka Višnjić (ARIS šifra 55934)

Gregory Caldwel Robson (ARIS šifra 54873)

Michel Lavrauw (ARIS šifra 57308)

Marko Orel (ARIS šifra 25610)

Bojan Kuzma (ARIS šifra 18893)

Michael Mrissa (ARIS šifra 51811)

Balazs David (ARIS šifra 51616)

Primož Šparl (ARIS šifra 23341)

Aleksander Malnič (ARIS šifra 02507)

 

Povzetek projekta:

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 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.