Recognizing pseudo-median graphs (Q5957357)

A median of a triple of vertices \(u, v, w\) of a graph is a vertex \(x\) such that \(x\) lies simultaneously on shortest paths joining \(u\) and \(v\), \(v\) and \(w\), and \(w\) and \(u\), respectively. A pseudo-median of \(u, v, w\) is a triple of mutually adjacent vertices \(x,y,z\) such that \(x,y \in I(u,v)\), \(x,z \in I(u,w)\) and \(y,z \in I(v,w)\) where \(I(a,b)\) consists of all vertices on shortest paths joining \(a\) and \(b\). A connected graph \(G\) is a median graph if every triple of vertices admits a unique median. \(G\) is a pseudo-median graph if every triple of vertices admits either a unique median or a unique pseudo-median. The author characterizes pseudo-median graphs and gives a recognition algorithm for these graphs in \(O(mn)\) time. Both characterization and recognition partly make use of results from a paper of \textit{H.-J. Bandelt} and \textit{H. M. Mulder} [Pseudo-median graphs: Decomposition via amalgamation and Carterian multiplication, Discrete Math. 94, No. 3, 161-180 (1991; Zbl 0743.05055)].