Geodetic Graph

Ore (1962) noted that not only does a tree possesses a unique shortest path between any two vertices, but that there also exist also other connected graphs having the same property. He termed all such graphs "geodetic graphs" and asked for a characterization of such graphs.

The numbers of geodetic graphs on , 2, ... nodes are 1, 1, 2, 4, 10, 23, 66, 185, 586, 1880, 6360, ... (OEIS A337179).

Examples of geodetic graphs include barbell graphs, cacti graph lacking even cycles (Gorovoy and Zmiaikou 2021), complete graphs  (Gorovoy and Zmiaikou 2021), odd cycle graphs  (Gorovoy and Zmiaikou 2021), lollipop graphs, trees (Gorovoy and Zmiaikou 2021), triangular snake graphs, and windmill graphs.

REFERENCES

Frasser, C. E. "-Geodetic Graphs and Their Application to the Topological Design of Computer Networks." In Proc. Argentinian Workshop on Theoretical Computer Science, 28 JAIIO-WAIT'99. pp. 187-203, 1999.

Gorovoy, D. and Zmiaikou, D. "On Graphs with Unique Geoodesics and Antipodes." 19 Nov 2021. https://arxiv.org/abs/2111.09987.

Ore, O. Theory of Graphs. Providence, RI: Amer. Math. Soc., 1962.

Parthasarathy, K. R. and Srinivasan, N. "Some General Constructions of Geodetic Blocks." J. Combin. Th. 33, 121-136, 1982.

Sloane, N. J. A. Sequence A337179 in "The On-Line Encyclopedia of Integer Sequences."Stemple, J. G.; and Watkins, M. E. "On Planar Geodetic Graphs." J. Combin. Th. 4, 101-117, 1968.