A distance-hereditary graph, also known as a completely separable graph, is a graph such that the distance matrix
of every connectedvertex-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.
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 Proc. Fourteenth Workshop on Analytic Algorithmics and Combinatorics (Ed.
C. Martínez and M. D. Ward). Philadelphia, PA: SIAM, pp. 31-45,
2017. https://doi.org/10.1137/1.9781611974775.3.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 
(Bandelt and Mulder 1986). For a disconnected
graph, apply this criterion to each connected
component.
,
2, ... vertices are 1, 1, 2, 6, 18, 73, 308, 1484,
7492, 40010, 220676, ... (OEIS A277862).
