Regular pseudo‐median graphs
Hans‐Jürgen Bandelt, Henry Martyn Mulder · Journal of Graph Theory · 1988
Abstract A graph is pseudo‐median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo‐median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper‐octahedron. Every self‐map of a pseudo‐median graph that preserves or collapses edges has an invariant regular pseudo‐median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo‐median graph induces a regular pseudo‐median subgraph.