Projekti / Programi
Strukture in algebraične lastnosti razredov grafov
| Koda |
Veda |
Področje |
Podpodročje |
| 1.01.05 |
Naravoslovje |
Matematika |
Teorija grafov |
| Koda |
Veda |
Področje |
| P110 |
Naravoslovno-matematične vede |
Matematična logika, teorija množic, kombinatorika |
graf, razdalja, konveksnost, diskretni metrični prostor, zastraženost, kartezični produkt, direktni produkt, mediana, kvazimedianski graf, tetivni graf, imprint, delna kocka, izometrični podgraf, retrakt, avtomorfizem
Raziskovalci (1)
| št. |
Evidenčna št. |
Ime in priimek |
Razisk. področje |
Vloga |
Obdobje |
Štev. publikacijŠtev. publikacij |
| 1. |
17005 |
dr. Boštjan Brešar |
Matematika |
Vodja |
2002 - 2004 |
403 |
Organizacije (1)
Povzetek
V projektu bomo raziskovali strukturne in algebraične lastnosti nekaterih pomembnih razredov grafov. Obravnavali bomo grafe, ki so definirani preko metričnih lastnosti, preko eliminacijskih postopkov, ali kot podgrafi grafovskih produktov. V ospredju raziskav bodo lastnosti, porojene z razdaljo v grafih, kot so konveksnost, zastraženost ter interval, odkrivali pa bomo karakterizacije razredov grafov preko prepovedanih podgrafov, preko ekvivalenčnih relacij definiranih na grafih in ostalih strukturnih lastnosti. Največje pozornosti bodo deležni medianski grafi in njihove posplošitve, še posebej kvazimedianski grafi ter delne kocke. Obravnavali bomo relacije na teh grafih, ki povezujejo število induciranih hiperkock z določenimi grafovskimi invariantami teh razredov. Raziskovali bomo strukturne lastnosti teh grafov, posebej pa nas bo zanimala ekspanzija. Preko ekspanzije lahko vpeljemo nove razrede grafov, raziskali bomo njihovo povezavo z dosedanjo teorijo. Obravnavali bomo razrede delnih kock, ki jih lahko prepoznamo učinkoviteje kot medianske grafe. Posebej nas bo zanimali razredi delnih kock, ki vsebuje medianske grafe in katerih regularni podrazred so natanko hiperkocke. Za te in sorodne razrede bomo raziskali, ali grafi teh razredov vsebujejo hiperkocko, ki je invariantna za avtomorfizme teh grafov. Obravnavali bomo razred posplošenih medianskih grafov kot izometričnih podgrafov kartezičnega produkta grafov, ki so zaprti za imprint. Raziskali bomo nekatere relevantne metrične lastnosti tega razreda z uporabo znanih metod in konceptov, ki so bili vpeljani pri obravnavi medianskih grafov. Obstoj posebnih invariantnih podgrafov za avtomorfizme grafov bomo raziskali za razrede grafov, ki so definirani preko določenih amalgamacijskih postopkov, kar bi posplošilo mnogo rezultatov. Poiskali bomo nekatere nove povezave med tetivnimi grafi in delnimi kockami v povezavi s presečnimi grafi maksimalnih kock. Obravnavali bomo strukturo grafov, ki se ne dajo predstaviti kot podgrafi kartezičnega produkta netrivialnih grafov in razrede grafov, ki jih lahko predstavimo kot direktni produkt dveh grafov.
