A distance-heredity graph, also known as a completely separable graph, is a graph such that the distance matrix of every connected vertex-induced subgraph of is the submatrix obtained from the distance matrix of itself corresponding to the subset of vertices . The name "distance-hereditary" derives from the fact that in such graphs, the induced subgraphs "inherit" the distance relationship from their parent graph.
A graph is distance-hereditary iff for any four vertices , , , , at least two of the sums
(1)
(2)
(3)
are equal, where denotes the graph distance from vertex to .
The numbers of connected distance-hereditary graphs on , 2, ... vertices are 1, 1, 2, 6, 18, 73, 308, 1484, 7492, 40010, 220676, ... (OEIS A277862).
Bahrani, M. and Lumbroso, J. "Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition." 4 Aug 2016. https://arxiv.org/abs/1608.01465.Bandelt, H.-J. and Mulder, H. M. "Distance-Hereditary Graphs." J. Combin. Th., Ser. B41, 182-208, 1986.Chauve, C.; Fusy, È.; and Lumbroso, J. "An Exact Enumeration of Distance-Hereditary Graphs" In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium On Discrete Algorithms, ANALCO session. SIAM, 2017.Gavrilyuk, A. L.; Nedela, R.; and Ponomarenko, I. "The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs." 24 May 2020. https://arxiv.org/abs/2005.11766.Howorka, E. "A Characterization of Distance-Hereditary Graphs." Quart. J. Math.28, 417-420, 1977.Howorka, E. "A Characterization of Ptolemaic Graphs." J. Graph Th.5, 323-331, 1981.Sachs, H. "On the Berge Conjecture Concerning Perfect Graphs." In Combinatorial Structures and their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969. Gordon and Breach, pp. 377-384, 1970.Sloane, N. J. A. Sequence A277862 in "The On-Line Encyclopedia of Integer Sequences."
such that the distance matrix of every connected vertex-induced subgraph 
of 
is the submatrix obtained from the distance matrix of 
itself corresponding to the subset of vertices 
. The name "distance-hereditary" derives from the fact that in such graphs, the induced subgraphs "inherit" the distance relationship from their parent graph. 
, 
, 
, 
, at least two of the sums 
denotes the graph distance from vertex 
to 
. 
, 2, ... vertices are 1, 1, 2, 6, 18, 73, 308, 1484, 7492, 40010, 220676, ... (OEIS A277862). 