主题
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. "交叉棱柱图。" 来自 MathWorld-- 资源。 https://mathworld.net.cn/CrossedPrismGraph.html

学科分类