Distance-hereditary graphs and signpost systems

An ordered pair (U,R)(U,R) is called a signpost system if UU is a finite nonempty set, R⊆U×U×UR⊆U×U×U, and the following axioms hold for all u,v,w∈Uu,v,w∈U: (1) if (u,v,w)∈R(u,v,w)∈R, then (v,u,u)∈R(v,u,u)∈R; (2) if (u,v,w)∈R(u,v,w)∈R, then (v,u,w)∉R(v,u,w)∉R; (3) if u≠vu≠v, then there exists t∈Ut∈U such that (u,t,v)∈R(u,t,v)∈R. (If FF is a (finite) connected graph with vertex set UU and distance function dd, then UU together with the set of all ordered triples (u,v,w)(u,v,w) of vertices in FF such that d(u,v)=1d(u,v)=1 and d(v,w)=d(u,w)−1d(v,w)=d(u,w)−1 is an example of a signpost system). If (U,R)(U,R) is a signpost system and GG is a graph, then GG is called the underlying graph of (U,R)(U,R) if V(G)=UV(G)=U and xy∈E(G)xy∈E(G) if and only if (x,y,y)∈R(x,y,y)∈R (for all x,y∈Ux,y∈U). It is possible to say that a signpost system shows a way how to travel in its underlying graph. The following result is proved: Let (U,R)(U,R) be a signpost system and let GG denote the underlying graph of (U,R)(U,R). Then GG is connected and every induced path in GG is a geodesic in GG if and only if (U,R)(U,R) satisfies axioms (4)–(8) stated in this paper; note that axioms (4)–(8)–similarly as axioms (1)–(3)–can be formulated in the language of the first-order logic.