主題
Search

Meyniel 圖


Meyniel 圖,也稱為非常強完美圖,是一種圖中,其中每個長度為五或更長的奇數環至少有兩條弦。Meyniel 圖是 完美圖

MeynielGraphs

頂點數為 n=1, 2, ... 的連通 Meyniel 圖的數量為 1, 1, 2, 6, 19, 88, 459, 3060, 23989, ... (上面展示了前幾個),而相應的非必要連通 Meyniel 圖的數量為 1, 2, 4, 11, 32, 130, 622, 3839, ... (OEIS A123434)。

根據定義,任何沒有長度 >=5 的奇數環的圖都是平凡的 Meyniel 圖。屬於 Meyniel 圖的圖類包括空圖(平凡地),完全圖(平凡地)。


另請參閱

圈的弦, 距離遺傳圖, 完美圖

使用 探索

參考文獻

Markosjan, S. E. and Karapetjan, I. "Perfect Graphs." Doklady Akademiya Nauk Armyanskoĭ SSR 63, 292-296, 1976.Meyniel, H. "On the Perfect Graph Conjecture." Disc. Math. 16, 339-342, 1976.Sloane, N. J. A. Sequence A123434 in "The On-Line Encyclopedia of Integer Sequences."

請引用為

Weisstein, Eric W. "Meyniel Graph." 來自 —— 資源。 https://mathworld.tw/MeynielGraph.html

主題分類