Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 23 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.