22
$\begingroup$

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.

$\endgroup$
25
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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