O neobstoju ekstremnih grafih / On the non-existence of extremal graphs
|
Naziv Tittle |
O neobstoju ekstremnih grafih / On the non-existence of extremal graphs |
|
Akronim Acronim |
BI-VB/23-25-002 |
|
Opis Description |
O NEOBSTOJU EKSTREMNIH GRAFIH Topologijo omrežja (na primer telekomunikacijskega, multiprocesorskega ali lokalnega računalniškega omrežja) po navadi modeliramo z grafom, katerega vozlišča predstavljajo vozlišča omrežja (postaje oz. procesorje), neusmerjene ali usmerjene povezave grafa pa predstavljajo povezave med danimi vozlišči. Pri načrtovanju takšnega omrežja moramo upoštevati številne značilnosti grafov. Najpogostejši takšni značilnosti sta omejitev stopnje vozlišč ter omejitev premera grafa. Interpretacija teh dveh parametrov v omrežju je očitna: stopnja vozlišča je število povezav, ki jih ima to vozlišče z drugimi vozlišči, premer pa predstavlja maksimalno število povezav, ki jih mora neko sporočilo prepotovati na poti med poljubnim parom vozlišč. Kakšno je največje število vozlišč v omrežju z omejeno stopnjo vozlišč in omejenim premerom? Če so povezave med vozlišči neusmerjene, potem imamo opravka z naslednjim problemom v teoriji grafov: • Problem stopnje in premera: Za dani naravni števili k in d poiščite največje možno število vozlišč n(k, d), za katero obstaja graf z n(k, d) vozlišči, ki ima največjo stopnjo k in premer d. Če besedo ‘stopnja’ zamenjamo z ‘izhodna stopnja’, dobimo različico problema za usmerjene grafe. Izhodna stopnja vozlišča v usmerjenemu grafu je število usmerjenih povezav z začetkom v danem vozlišču. Tako dobimo naslednji problem: • Problem stopnje in premera v usmerjenemu grafu: Za dani naravni števili d in k poiščite največje možno število vozlišč n(d,k), za katero obstaja usmerjeni graf z n(d,k) vozlišči, ki ima najvčjo izhodno stopnjo d in premer k. Problem kletke, ki je znan tudi kot problem stopnje in ožine, je tesno povezan s problemom stopnje in premera. • Problem kletke (Problem stopnje in ožine): Za dani naravni števili k in g poiščite najmanjše število vozlišč n(k, g) za katero obstaja graf stopnje k in ožine g. V tem projektu se bomo osredotočili na odprta vprašanja in probleme, ki se nanašajo na problem kletke ter na problem stopnje in premera v neusmerjenih in usmerjenih grafih. Bolj natančno, bomo obravnavali 4 povezanih tem iz ekstremalne teorije grafov. Obravnavali bomo dobro znani problem kletk na posebnem razredu vozliščno-tranzitivnih grafov. Bomo podali negativen odgovor na naslednjo odprto vprašanje: Naj bo vt(k,d) red največjega vozliščno-tranzitivnega k-regularnega grafa z premerom d. Ali je res da velja vt(k,d)=n(k,d) za neskončno mnogu parov k>2 in d>2 ? Obstaja upanje da bomo z spektralne analize uspeli pokazati neobstoja največjega Moorevjega grafa G. Načrt je, izpeljati formule za večkratnost pripadajočih lastnih vrednosti določenega grafa H, ki je podgraf grafa G, in nato izpeljati relacije med njimi. V tem projektu združili bomo spektralne analize in preštevanja g-ciklov v (k, g)-grafih z presežkom 6, da bi prišli do potrebnih pogojev, ki morajo veljati za parametra k in g. Ta pristop bo uporabljen za izboljšanje spodnje meje za red kletk sode ožine. Z drugimi besedami, pokazali bomo da je presežek kateregakoli k-regularnega grafa ožine g večji od 6. Znano je, če d>δ>k+1>3, potem ne obstaja (d,k,δ)-digraf, ki vsebuje samo samoponovitve. V tem projektu bomo izboljšali zgornji rezultat, oziroma, pokazali bomo, če d ≥ δ ≥ 2 potem ne obstaja noben (d, k, δ)-digraf, ki vsebuje samo samoponovitve. |
|
Trajanje Duration |
01/05/2023 - 30/04/2025 |
|
Vodja projekta Project Leader |
Slobodan Filipovski |
|
Sodelujoče organizacije Participating organizations |
Open University (Milton Keynes) |
|
Oddelek Department |
Oddelek za matematiko IAM |