Geodetic graph
From Wikipedia, the free encyclopedia
In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.
Geodetic graphs were introduced in 1962 by Øystein Ore, who observed that they generalize a property of trees (in which there exists a unique path between each two vertices regardless of distance), and asked for a characterization of them.[1] Although these graphs can be recognized in polynomial time, "more than sixty years later a full characterization is still elusive".[2]
Every tree,[1] every complete graph,[3] and every odd-length cycle graph is geodetic.[4]
If is a geodetic graph, then replacing every edge of by a path of the same odd length will produce another geodetic graph.[5] In the case of a complete graph, a more general pattern of replacement by paths is possible: choose a non-negative integer for each vertex , and subdivide each edge by adding vertices to it. Then the resulting subdivided complete graph is geodetic, and every geodetic subdivided complete graph can be obtained in this way.[6][7]
Related graph classes
If every biconnected component of a graph is geodetic then the graph itself is geodetic. In particular, every block graph (graphs in which the biconnected components are complete) is geodetic.[3] Similarly, because a cycle graph is geodetic when it has odd length, every cactus graph in which the cycles have odd length is also geodetic. These cactus graphs are exactly the connected graphs in which all cycles have odd length. More strongly, a planar graph is geodetic if and only if all of its biconnected components are either odd-length cycles or geodetic subdivisions of a four-vertex clique.[4]
