Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Geodetic graph
open-in-new
<p>In graph theory, a geodetic graph is an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> such that there exists a unique (unweighted) <a href="/facts/Shortest_path/g4nsrswr">shortest path</a> between each two vertices. </p><p>Geodetic graphs were introduced in 1962 by <a href="/facts/%25C3%2598ystein_Ore/mSpYnM3U">Øystein Ore</a>, 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. Although these graphs can be recognized in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, "more than sixty years later a full characterization is still elusive". </p>