Indeks razdaljne neuravnoteženosti grafov : magistrsko delo

Uranič, Nuša (author), Šparl, Primož (mentor)

V magistrskem delu najprej predstavimo pojem razdaljno uravnoteženega grafa ter si pogledamo nekaj primerov takih grafov in primer družine grafov, kjer noben član ni razdaljno uravnotežen. Nato predstavimo naravno posplošitev tega koncepta ter tako pridemo do l-razdaljno uravnoteženih grafov. Tu si za primer najprej pogledamo Cayleyeve grafe Abelovih grup, ki so povsem razdaljno uravnoteženi, nato pa se osredotočimo na posplošene Petersenove grafe. V nadaljevanju pridemo preko tako imenovanega Mostarjevega indeksa do indeksa razdaljne neuravnoteženosti ter določimo vrednosti tega indeksa za poti in polne večdelne grafe ter nato še za dve manj znani družini grafov. Da so navedene vrednosti pravilne, tudi teoretično dokažemo. Zatem predstavimo nekaj rezultatov in domnev glede najmanjšega in drugega najmanjšega možnega indeksa razdaljne neuravnoteženosti za drevesa danega reda. Za konec predstavimo dokaz izreka, ki nam pove, da je med vsemi drevesi reda n, kjer je n>=5, zvezda S_{n-1} edino drevo reda n z najmanjšim možnim indeksom razdaljne neuravnoteženosti.

• Language: Slovenian
• Keywords: l-razdaljno uravnotežen graf, indeks razdaljne neuravnoteženosti, drevo, matematika
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Place of publishing: Ljubljana
• Publisher: N. Uranič
• Year: 2024
• Number of pages: 82 str.
• PID: 20.500.12556/RUL-158719
• UDC: 51(043.2)
• COBISS.SI-ID: 199563267
• Publication date in RUL: 19.06.2024

URANIČ, Nuša, 2024, Indeks razdaljne neuravnoteženosti grafov : magistrsko delo [online]. Master’s thesis. Ljubljana : N. Uranič. [Accessed 8 April 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=158719

Secondary language

• Language: English
• Title: Distance-Unbalancedness Index of Graphs

Abstract

In this master's thesis we firstly introduce the concept of a distance-balanced graph. Then we present some examples of distance-balanced graphs and a family of graphs, no member of which is distance-balanced. We then make a natural generalization of this concept to define l-distance-balanced graphs. Here, as an example, we look at Cayley graphs of abelian groups, which are all highly distance-balanced. Then we focus on generalized Petersen graphs. In the second main part of the thesis we generalize the so-called Mostar index to define the distance-unbalancedness index of a graph. Here we first compute this index for paths and complete multipartite graphs and then also for some lesser-known families of graphs. After that we present a few results and conjectures regarding the smallest and the second smallest possible value of the distance-unbalancedness index for trees of given order. Finally, we present the proof of the theorem showing that among all trees of order n, where n>=5, the star S_{n-1} is the unique tree of order n with the smallest possible value of the distance-unbalancedness index.

• Keywords: l-distance-balanced graph, distance-unbalancedness index, tree