Seminar of Graph Theory - Valter Cingel (23.4.2026)
Thursday 23.4.2026 at 9:50, Lecture room M 213
Valter Cingel:
Uniform routings of shortest paths in graphs with large automorphism groups
Abstract:
In this presentation, we focus on 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} (briefly, URSP).
The main goal of our research 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 Moore graphs. 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. We also focus on geodetic graphs which are defined to have just a single unique shortest path between every pair of vertices. We present a classification of planar geodetic graphs with respect to the existence of a URSP. Finally, we construct infinite families of graphs admitting a URSP that are neither vertex-transitive nor regular.
(Joint work with Róbert Jajcay.)