主題
Search

交叉稜柱圖


CrossedPrismGraph

對於正偶數 nn-交叉稜柱圖(此處首次引入的術語)是透過取兩個不相交的迴圈圖 C_n 並新增邊 (v_k,v_(2k+1))(v_(k+1),v_(2k)),其中 k=1, 3, ..., (n-1) 而獲得的圖。

交叉稜柱圖是 三次頂點傳遞 的(因此出現在 Read 和 Wilson 1998 年的著作中,儘管沒有任何指定表明其屬於特殊的圖族),弱正則哈密頓哈密頓可分解 的。2n-交叉稜柱圖對於 n>2環面的 (E. Weisstein, 2023 年 5 月 9 日)。

Simmons (2014) 使用術語 “4m 個頂點的多邊形二部圖” 來表示與 m-交叉稜柱圖同構的圖,並研究了這些圖中 哈密頓可分解性哈密頓路徑 的結構。

前幾個交叉稜柱圖及其一些屬性在 Wolfram 語言 中實現為GraphData[{"CrossedPrism", n}].

n-交叉稜柱圖具有 獨立多項式

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

其具有遞推方程

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

n-交叉稜柱圖與 Haar 圖 H(2^(n+1)+2^(n/2)+1) 以及 (1,2n,n-1)-蜂巢環面圖 同構。下表總結了其他特殊情況。


另請參閱

交叉圖, 迴圈圖, 三次頂點傳遞圖, 立方圖, 富蘭克林圖, 舵輪圖, 蜂巢環面圖, 梯形圖, 莫比烏斯梯子, 稜柱圖, 網狀圖

使用 探索

參考文獻

Read, R. C. 和 Wilson, R. J. "Cubic Polyhedral Graphs: 8-16 Vertices." 在 An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 159-163, 1998.Simmons, G. J. "A Surprising Regularity in the Number of Hamilton Paths in Polygonal Bigraphs." Ars Combin. 115, 335-341, 2014.

在 上被引用

交叉稜柱圖

請引用本文為

Weisstein, Eric W. "交叉稜柱圖。" 來自 Web 資源。 https://mathworld.tw/CrossedPrismGraph.html

學科分類