主題
Search

中間層圖


MiddleLayerGraphs

階數為 n 的中間層圖是頂點傳遞圖,其頂點集由長度為 2n+1 且恰好有 nn+1 個條目等於 1 的所有位串組成,當且僅當兩個頂點對應的位串恰好在一個位上不同時,它們之間存在一條邊 (Mütze 2016)。中間層圖對於每個 n>=1 都具有哈密頓環的猜想(現已證明)被稱為中間層猜想

中間層圖對應於二分 Kneser 圖 H(2n+1,n)。它是最稀疏的二分 Kneser 圖,因此在某種意義上是證明此類圖族哈密頓性的最難障礙 (Mütze 2016)。特殊情況總結在下表中。

中間層圖是二分的、連通的,並且有 (2n+1; n)+(2n+1; n+1) 個頂點 (Mütze 2016)。

階數為 n 的中間層圖在 Wolfram 語言中實現為GraphData[{"MiddleLayer", n}].


另請參閱

二分 Kneser 圖, Danzer 圖, Desargues 圖, 中間層猜想, 非哈密頓頂點傳遞圖

使用 探索

參考文獻

Knuth, D. Exercise 56, §7.2.1.3 in The Art of Computer Programming, Vol. 4A. Reading, MA: Addison-Wesley, 2011.Mütze, T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc. 112, 677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.

請引用本文為

Weisstein, Eric W. "Middle Layer Graph." 來自 Web 資源。 https://mathworld.tw/MiddleLayerGraph.html

學科分類