22

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.

László Kozma
  • 1,336
  • 1
  • 10
  • 16

2 Answers2

25

According to Information System on Graph Classes and their Inclusions, these graphs are studied under the name “geodetic graphs.”

Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
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.

Juho
  • 3,170
  • 2
  • 26
  • 36