Distance-hereditary graphs and signpost systems (Q960964)

An ordered pair \((U,R)\) is called a signpost system if \(U\) is a finite nonempty set, \(R\subseteq U\times U\times U\), and the following axioms hold for all \(u,v,w\in U\): {\parindent=6mm \begin{itemize}\item[(1)]if \((u,v,w)\in R\), then \((v,u,u)\in R\); \item[(2)]if \((u,v,w)\in R\), then \((v,u,w)\not\in R\); \item[(3)]if \(u\not= v\), then there exists \(t\in U\) such that \((u,t,v)\in R\). \end{itemize}} (If \(F\) is a (finite) connected graph with vertex set \(U\) and distance function \(d\), then \(U\) together with the set of all ordered triples \((u,v,w)\) of vertices in \(F\) such that \(d(u,v)=1\) and \(d(v,w)=d(u,w)-1\) is an example of a signpost system). If \((U,R)\) is a signpost system and \(G\) is a graph, then \(G\) is called the underlying graph of \((U,R)\) if \(V(G)=U\) and \(xy\in E(G)\) if and only if \((x,y,y)\in R\) (for all \(x,y\in U\)). It is possible to say that a signpost system shows a way how to travel in its underlying graph. A graph \(G\) is called distance-hereditary if, for any connected induced subgraph \(H\) of \(G\), the distance between two vertices in \(H\) equals their distance in \(G\). The following result is proved: Let \((U,R)\) be a signpost system and let \(G\) denote the underlying graph of \((U,R)\). Then \(G\) is connected and distance-hereditary if and only if \((U,R)\) satisfies the following axioms: {\parindent=6mm \begin{itemize}\item[(4)]if \((u,v,w), (w, x, v)\in R\), then \((u, v, x)\in R\); \item[(5)]if \((u, v, v), (u,w,v)\in R\), then \(w = v\); \item[(6)]if \((v,w,u), (w, x, u)\in R\), then \((x, v, v)\not\in R\); \item[(7)]if \((v,w, u), (w, x, u), (x, y, u)\in R\), then \((y, v, v)\not\in R\); \item[(8)]if \((u, v,w), (w, x, x)\in R\), \(u\not= x\), and \((x, u, u)\not\in R\), then \((u, v, x)\in R\). \end{itemize}}