N1-0285 Metrični problemi v grafih in hipergrafih

FMF_ARRS

Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.

Članica UL: Fakulteta za matematiko in fiziko

Šifra projekta: N1-0285

Naziv projekta: Metrični problemi v grafih in hipergrafih

Obdobje: 1. 1. 2023 - 31. 12. 2025

Letni obseg: 0,6 FTE, cenovna kategorija: C

Vodja: Sandi Klavžar

Veda: Naravoslovje

Sodelujoče RO, sestava projektne skupine in bibliografske reference

Vsebinski opis projekta:

Cilj projekta je pomembno prispevati k metrični teoriji grafov in razširiti teorijo na hipergrafe. Najprej bomo rešili postavljene odprte probleme na grafih in nato raziskali, ali jih je mogoče tako ali drugače razširiti na hipergrafe ali na posebne hipergrafe, ki omogočajo takšne razširitve, kot so na primer linearni hipergrafi. Specifične cilje projekta je mogoče združiti v naslednje štiri zaokrožene večje cilje.

(1) Raziskovanje Wienerjevega indeksa. Ker lahko Wienerjev indeks izrazimo kot polovico celotne razdalje njegovih vozlišč, bomo posebno pozornost namenili celotnim razdaljam vozlišč. Posebej bodo raziskani grafi, v katerih imajo vozlišča paroma različne celotne razdalje. Invariante, ki temeljijo na razdalji in so podobne Wienerjevemu indeksu, bodo prav tako natančno preučene. Ker se je prerezna metoda izkazala za izjemno uporabno za raziskovanje Wienerjevega indeksa grafov in dodatnih invariant grafov, ki temeljijo na razdalji, je naš cilj razširiti to teorijo na hipergrafe.

(2) Raziskovanje metrične dimenzije. Raziskali bomo različne inačice klasične metrične dimenzije, vključno z povezavno metrično dimenzijo in mešano metrično dimenzijo. Posebna pozornost bo namenjena metrični dimenziji zasnovani na multimnožicah. Na hipergrafih bomo raziskali tako klasično metrično dimenzijo kot tudi njene različice ter skušali pridobljene rezultate za povezavno metrično dimenzijo in mešano metrično dimenzijo razširiti z grafov na hipergrafe.

(3) Raziskovanje krepkega (povezavnega) geodetskega števila. Načrtujemo razširitev znanih rezultatov za krepko geodetsko število in krepko povezavno geodetsko število za kartezične grafe produkta. Ti dve invarianti nameravamo raziskati na drugih standardnih grafovskih produktih in drugih družinah grafov. Krepki povezavni geodetski problem bo raziskan na polnih dvodelnih grafih. Za splošne grafe želimo najti ostre zgornje in spodnje meje za krepko (povezavno) geodetsko število. Krepko geodetsko število in krepko povezavno geodetsko število bosta primerjana med seboj. Novo pridobljene in znane rezultate bomo razširili z grafov na hipergrafe.

(4) Raziskovanje problema splošne lege. Nadaljevali bomo z raziskavo problema splošne lege na vozliščih in pričeli z raziskavo problema splošne lege na povezavah. Oba problema bomo razširili na hipergrafe z razširitvijo znanih rezultatov, kadar koli bo to mogoče, pa tudi z razširitvijo novih rezultatov, ki jih bomo dokazali za grafe. V posebnem nameravamo karakterizirati množice v splošni legi v hipergrafih ter raziskati število splošne lege in povezavno število splošne lege na hipergrafih z drevesno strukturo in na hipergrafih s strukturo produkta.