Distance-hereditary graphs (Q1084114): Difference between revisions

A distance-hereditary graph is a connected graph in which every induced path is isometric, that is, the distance between any two vertices in an induced path equals their distance in the graph. A block graph is a conncted graph in which every block (i.e., maximal 2-connected subgraph) is complete. Let G be a graph with distance function d. Then d is said to satisfy the four-point condition if for any four vertices u, v, w, x the larger two of the three distance sums \(d(u,v)+d(w,x)\), \(d(u,w)+d(v,x)\) and \(d(u,x)+d(v,w)\) are equal. An induced subgraph H of a graph G is said to be an isometric subgraph if for any two vertices u, v of H the distance between u and v in H equals the distance between u and v in G. The authors show that if G is a connected graph having distance function d, then the following conditions are equivalent: (i) G is a block graph, (ii) d satisfies the four-point condition and (iii) neither \(K_ 4\) minus an edge nor any circuit \(C_ n\) with \(n\geq 4\) is an isometric subgraph of G. It is also shown that the finite distance-hereditary graphs of order at least 2 are precisely those graphs which are obtained by applying a sequence of extensions (which are described in the paper) to \(K_ 2\). Several consequences of this result are addressed. Moreover, distance-hereditary graphs are characterized in terms of the distance function d, or via forbidden isometric subgraphs.