主題
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 圖, 頂點匯出子圖

使用 探索

參考文獻

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." 來自 Web 資源. https://mathworld.tw/Distance-HereditaryGraph.html

主題分類