| Meno: | Valter |
|---|---|
| Priezvisko: | Cingel |
| Názov: | Uniform routings of shortest paths in graphs with large automorphism groups |
| Vedúci: | prof. RNDr. Róbert Jajcay, DrSc. |
| Rok: | 2026 |
| Kµúčové slová: | graph, symmetry, automorphism group, uniform routing of shortest paths, Moore graphs, geodetic graphs |
| Abstrakt: | In this thesis we study uniform routings of shortest paths in graphs and their relationship to structural symmetry. Given a connected graph $\Gamma$ with $n$ vertices, a routing is a collection of $n(n-1)$ oriented paths joining every ordered pair of distinct vertices. If all these paths are shortest paths and every vertex appears as an inner vertex in the same number of paths, the routing is called a \emph{uniform routing of shortest paths} (URSP). Equivalently, a URSP is a routing of shortest paths for which the vertex-forwarding index attains its minimum possible value and is equal for all vertices. The main goal of this thesis is to investigate which structural and symmetry conditions ensure the existence of a URSP. Graphs with large (at least vertex-transitive) groups of automorphisms can be considered to contain a lot of structural symmetry. Therefore, we focus on the relationship between large automorphism groups and the existence of URSPs. Moreover, some of our results do not assume large automorphism groups, and they demonstrate that URSPs can arise independently of the automorphism symmetry. We devote particular attention to \emph{Moore graphs}, an infinite class of graphs meeting the \emph{Moore bound}, a combinatorial lower bound on the smallest order of a graph with given valency and girth. We prove that Moore graphs of odd girth admit a unique URSP and that Moore graphs of even girth with a Hamiltonian cycle also admit a URSP. This leads to the existence of regular graphs that are not vertex-transitive, but nevertheless admit a URSP. When considering another class of graphs called \emph{geodetic graphs}, graphs with a single unique shortest path between every pair of vertices, we show that vertex-transitivity guarantees the existence of a URSP, and we provide a classification of planar geodetic graphs admitting a URSP. Finally, we construct infinite families of graphs admitting a URSP that are neither vertex-transitive nor regular. |
Súbory diplomovej práce:
Autor nedal súhlas so zverejnením svojej diplomovej práce.
Súbory prezentácie na obhajobe:
| cingel_prezentacia_SVK.pdf |