主題
Search

莫比烏斯梯子


MoebiusLadders

莫比烏斯梯子,有時也稱為莫比烏斯輪(Jakobson 和 Rivin 1999),階數為 n 的莫比烏斯梯子是透過在階數為 n 的稜柱圖 中引入扭曲而獲得的簡單圖,該稜柱圖同構於迴圈圖 Ci_(2n)(1,n)。莫比烏斯梯子有時表示為 M_n

4-莫比烏斯梯子被稱為瓦格納圖(2n-1)-莫比烏斯梯子梯級圖同構於 Haar 圖 H(2^(2n)+1)

莫比烏斯梯子是哈密頓圖優美圖 (Gallian 1987, Gallian 2018),並且根據構造,是單交叉圖。莫比烏斯梯子也是非平凡的雙平面圖

對於 n=3, 4, ...,有向哈密頓環的數量為 12, 10, 16, 14, 20, 18, 24, ... (OEIS A124356),由閉合形式給出

 |HC(n)|=2[(n+2)-(-1)^n].
(1)

n-莫比烏斯梯子圖具有獨立多項式

 I_n(x)=2^(-n)[-2^n(-x)^n+(x-sqrt(x(x+6)+1)+1)^n+(x+sqrt(x(x+6)+1)+1)^n].
(2)

獨立多項式匹配多項式的遞推方程由下式給出

I_n(x)=I_(n-1)(x)+x(x+2)I_(n-2)(x)+x^2I_(n-3)(x)
(3)
mu_n(x)=(x^2-1)mu_(n-1)(x)+2(1-x^2)mu_(n-2)(x)+(x^2+1)mu_(n-3)(x)-mu_(n-4)(x).
(4)

n-莫比烏斯梯子的二部雙圖稜柱圖 Y_(2n)M_n圖平方迴圈圖 Ci_(2n)(1,2,n-1,n),其圖立方Ci_(2n)(1,2,3,n-2,n-1,n)


另請參閱

迴圈圖, 交叉稜柱圖, Helm 圖, 梯子圖, 稜柱圖, 瓦格納圖, Web 圖, 輪圖

使用 探索

參考文獻

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 20-21, 1993.Gallian, J. "Labeling Prisms and Prism Related Graphs." Congr. Numer. 59, 89-100, 1987.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 118 and 131, 2001.Hladnik, M.; Marušič, D.; and Pisanski, T. "Cyclic Haar Graphs." Disc. Math. 244, 137-153, 2002.McSorley, J. P. "Counting Structures in the Moebius Ladder." Disc. Math. 184, 137-164, 1998.Jakobson, D. and Rivin, I. "On Some Extremal Problems in Graph Theory." 8 Jul 1999. http://arxiv.org/abs/math.CO/9907050.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 270, 1998.Sloane, N. J. A. Sequence A124356 in "The On-Line Encyclopedia of Integer Sequences."

請引用為

Weisstein, Eric W. “莫比烏斯梯子。” 來自 Web 資源。 https://mathworld.tw/MoebiusLadder.html

主題分類