Projekti / Programi
Topološka in metrična teorija grafov
Koda |
Veda |
Področje |
Podpodročje |
1.01.00 |
Naravoslovje |
Matematika |
|
Koda |
Veda |
Področje |
P110 |
Naravoslovno-matematične vede |
Matematična logika, teorija množic, kombinatorika |
graf, vložitev grafa, rod grafa, povezavna širina, celična širina, prekrižno število, minor grafa, barvanje, pretok, razdalja, konveksnost, diskretni metrični prostor, kartezični produkt, direktni produkt, medianski graf, delna kocka, izometrični podgraf, avtomorfizem
Raziskovalci (25)
Organizacije (1)
Povzetek
V prvem delu projekta bomo obravnavali lastnosti grafov, ki so vloženi na ploskve. Zanimale nas bodo lastnosti grafov, katerih vložitve so lokalno ravninske, predvsem v povezavi s pojmi povezavne in celične širine ter njune posplošitve - neseparacijske širine. V zvezi s teorijo grafovskih minorjev bomo raziskovali prekrižno število, neizbežne strukture v velikih grafih in prepovedane minorje za nekatere minorsko zaprte družine. Raziskovali bomo spektralne lastnosti (vloženih) grafov, predvsem glede na Laplaceov operator grafa. Ukvarjali pa se bomo še z barvanji grafov, predvsem s seznamskimi barvanji, neponavljajočimi barvanji, krožnim kromatičnim številom in s pretoki v grafih.
V drugem delu projekta bomo obravnavali razrede grafov, ki so definirani preko metričnih lastnosti, ali za katere obstaja faktorizacija, z ozirom na grafovske produkte. Obdelali bomo faktorizacije hiperkock glede na direktni produkt ter preučili pogoje za posplošitve tovrstnih faktorizacij na poljubne kartezične produkte grafov ter na medianske grafe. Obravnavali bomo delne kocke, njihove podrazrede, ki so sorodni medianskim grafom ter podrazred regularnih delnih kock. V povezavi z domnevo o gracilnih drevesih bomo uvedli novo označitev delnih kock in preučevali vprašanje, ali vse delne kocke dopuščajo posplošeno gracilno označitev. Nadaljevali bomo z raziskavami polinoma kock za medianske grafe in raziskali zveze med ničlami tega polinoma in pomembnimi razredi medianskih grafov. Obravnavali bomo grafovske invariante na kartezičnem produktu grafov, še posebej večkratno dominacijo in ugotavljali povezave teh rezultatov, z ozirom na Vizingovo domnevo o dominantnem številu kartezičnega produkta grafov.