主题
Search

距离遗传图


距离遗传图,也称为完全可分图,是一个图 G,使得每个连通的顶点导出子图 G_V距离矩阵是从 G 自身的距离矩阵获得的子矩阵,对应于顶点子集 V。 “距离遗传” 这个名称源于这样一个事实:在这样的图中,导出子图 “继承” 了其父图的距离关系。

一个图是距离遗传的 当且仅当 对于任意四个顶点 uvwx,至少有以下两个和

d_1=d(u,v)+d(w,x)
(1)
d_2=d(u,w)+d(v,x)
(2)
d_3=d(u,x)+d(v,w)
(3)

相等,其中 d(i,j) 表示从顶点 ij 的图距离。

DistanceHereditaryGraphs

具有 n=1, 2, ... 个顶点的连通距离遗传图的数量分别是 1, 1, 2, 6, 18, 73, 308, 1484, 7492, 40010, 220676, ... (OEIS A277862)。

距离遗传图是 完美图Meyniel 图

属于距离遗传图的图类包括 块图

距离遗传图的 Weisfeiler-Leman 维度 为 1 或 2 (Gavrilyuk et al. 2020)。


另请参阅

Meyniel 图, 完美图, Ptolemaic 图, 顶点导出子图

使用 Wolfram|Alpha 探索

参考文献

Bahrani, M. 和 Lumbroso, J. "Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition." 2016 年 8 月 4 日. https://arxiv.org/abs/1608.01465.Bandelt, H.-J. 和 Mulder, H. M. "Distance-Hereditary Graphs." J. Combin. Th., Ser. B 41, 182-208, 1986.Chauve, C.; Fusy, È.; 和 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.; 和 Ponomarenko, I. "The Weisfeiler-Leman Dimension of Distance-Hereditary Graphs." 2020 年 5 月 24 日. 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."

请将此引用为

Weisstein, Eric W. "Distance-Hereditary Graph." 来自 MathWorld--Wolfram Web 资源. https://mathworld.net.cn/Distance-HereditaryGraph.html

主题分类