login
| SL

Hamiltonski cikli z rotacijsko simetrijo v povezanih točkovno tranzitivnih grafih / Hamilton cycles with rotational symmetry in connected vertex-transitive graphs

Naziv

Tittle

Hamiltonski cikli z rotacijsko simetrijo v povezanih točkovno tranzitivnih grafih / Hamilton cycles with rotational symmetry in connected vertex-transitive graphs

Akronim

Acronim

J1-50000

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.

Vrsta projekta

Project Type

Temeljni projekt

Trajanje

Duration

01/10/2023 - 30/09/2026

URL

URL

Vodja projekta

Project Leader

Dragan Marušič

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)

Oddelek

Department

UP
University of Primorska

Andrej Marušič Institute
UP IAM

Muzejski trg 2
6000 Koper
Slovenia

tel.: +386 (0)5 611 75 91
fax.: +386 (0)5 611 75 92
e-mail: info@iam.upr.si
Copyright
Accessibility statement