Geodetic Graphs: Experiments and New Constructions

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.