TOPICS
Search

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.

GeodeticGraphs

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

Examples of geodetic graphs include barbell graphs, block graphs, cacti graph lacking even cycles (Gorovoy and Zmiaikou 2021), complete graphs K_n (Gorovoy and Zmiaikou 2021), odd cycle graphs C_(2n+1) (Gorovoy and Zmiaikou 2021), lollipop graphs, trees (Gorovoy and Zmiaikou 2021), triangular snake graphs, and windmill graphs.


See also

Antipodal Graph, Graph Distance Matrix

Explore with Wolfram|Alpha

References

Frasser, C. E. "k-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.

Cite this as:

Weisstein, Eric W. "Geodetic Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GeodeticGraph.html

Subject classifications