Geodetic Graphs: Experiments and New Constructions
Florian Stober, Armin Weiß
Source abstract
In 1962 Ore initiated the study of geodetic graphs. A graph is called geodetic if the shortest path between every pair of vertices is unique. In the subsequent years a wide range of papers has appeared investigating their peculiar properties. Yet, a complete classification of geodetic graphs remains out of reach. In this work we present an exhaustive search algorithm for enumerating all biconnected geodetic graphs of a given order. Using our program, we find all geodetic graphs with up to 25 vertices and all regular geodetic graphs with up to 32 vertices. This leads to the discovery of a new infinite family of geodetic graphs. Moreover, we present a new result on constructing geodetic subdivisions of geodetic graphs.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.