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).
