TOPICS

Distance-Hereditary Graph

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

Distance-hereditary graphs are perfect and Meyniel graphs.

Classes of graphs that are distance-hereditary include block graphs and trees.

Distance-hereditary graphs have Weisfeiler-Leman dimension 1 or 2 (Gavrilyuk et al. 2020).

Meyniel Graph, Perfect Graph, Ptolemaic Graph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

More things to try:

References

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. B 41, 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."

Cite this as:

Weisstein, Eric W. "Distance-Hereditary Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Distance-HereditaryGraph.html