<p>Such graphs are indeed geodetic. A graph is bigeodetic, if there are at most two shortest paths between any pair of vertices. In general, a graph is $k$-geodetic if there are at most $k$ shortest paths between any pair of vertices.</p>

<p>Another example of an geodetic graph is a block graph. A graph is a block graph if it can be constructed from a tree by replacing every edge with a clique. Equivalently, this is known as a diamond-free chordal graph. A diamond is a $K_4$ minus an edge. For example, see Theorem 1.1 in <a href="http://www.sciencedirect.com/science/article/pii/S0012365X09004300">Le, Van Bang, and Nguyen Ngoc Tuy. "The square of a block graph." Discrete Mathematics 310.4 (2010): 734-741.</a></p>

CC BY-SA 3.0
2013-05-16T15:22:36.270Z
2013-05-16T15:22:36.270Z
Juho
<p>According to Information System on Graph Classes and their Inclusions, these graphs are studied under the name “<a href="http://www.graphclasses.org/classes/gc_96.html">geodetic graphs</a>.”</p>

CC BY-SA 3.0
2013-02-04T16:05:00.890Z
2013-02-04T16:05:00.890Z
Tsuyoshi Ito
<p>I'm looking for undirected, unweighted, connected graphs $G=(V,E)$, in which for every pair $u,v \in V$, there is a unique $u \rightarrow v$ path that realizes the distance $d(u,v)$.</p>

<p>Is this class of graphs well-known? What other properties does it have? For example, every tree is of this kind, as well as every graph without an even cycle. However, there are graphs containing even cycles that are of this kind.</p>

<graph-theory>
Graphs in which all shortest paths are unique
László Kozma
# Graphs in which all shortest paths are unique

(Asked by: username_0 on 2013-02-04)

I'm looking for undirected, unweighted, connected graphs $G=(V,E)$, in which for every pair $u,v \in V$, there is a unique $u \rightarrow v$ path that realizes the distance $d(u,v)$.

Is this class of graphs well-known? What other properties does it have? For example, every tree is of this kind, as well as every graph without an even cycle. However, there are graphs containing even cycles that are of this kind.

**Tags:** graph-theory

---

## 2 answers

### Answer by username_2 on 2013-02-04. Score: 25 | Accepted answer

According to Information System on Graph Classes and their Inclusions, these graphs are studied under the name “[geodetic graphs](http://www.graphclasses.org/classes/gc_96.html).”


---

### Answer by username_1 on 2013-05-16. Score: 10

Such graphs are indeed geodetic. A graph is bigeodetic, if there are at most two shortest paths between any pair of vertices. In general, a graph is $k$-geodetic if there are at most $k$ shortest paths between any pair of vertices.

Another example of an geodetic graph is a block graph. A graph is a block graph if it can be constructed from a tree by replacing every edge with a clique. Equivalently, this is known as a diamond-free chordal graph. A diamond is a $K\_4$ minus an edge. For example, see Theorem 1.1 in [Le, Van Bang, and Nguyen Ngoc Tuy. "The square of a block graph." Discrete Mathematics 310.4 (2010): 734-741.](http://www.sciencedirect.com/science/article/pii/S0012365X09004300)


---

