主题
Search

棱柱图


PrismGraph

棱柱图是对应于 骨架,该骨架是 n-棱柱。 因此,棱柱图既是 平面 的,也是 多面体 的。 一个 n-棱柱图有 2n 个节点和 3n 条边。 n-棱柱图与 广义 Petersen 图 P_(n,1) 以及 图的笛卡尔积 P_2 square C_n 同构,其中 P_2 是两个节点上的 路径图,而 C_nn 个节点上的 环图。 因此,棱柱图是 KC 图 的一个特例。

对于棱柱图,似乎没有标准的表示法。 它被不同地表示为 Y_n(本作品),D_n(Gallian 1987),Pi_n(Hladnik et al. 2002),或 CL_n(Gross 和 Yellen 1999,第 14 页,代表“circular ladder”)。

对于奇数 nn-棱柱与 循环图 Ci_(2n)(2,n) 同构,这可以通过将内环旋转 180 degrees 并增加其半径以等于上方顶部嵌入中的外环半径来看出。 此外,对于奇数 nY_nCi_(2n)(4,n)Ci_(2n)(6,n)、...、Ci_(2n)(n-1,n) 同构。

棱柱图 Y_n 等价于 二面体群 D_(2n) 关于生成集 {x,x^(-1),y}凯莱图 (Biggs 1993, p. 126)。

棱柱图 Y_3完全二部图 K_(2,3)线图。 棱柱图 Y_4立方图 同构。 2n-棱柱图与 Haar 图 H(2^2n-1+3) 同构。

由于是 单位距离图图的笛卡尔积,棱柱图本身也是一个 单位距离图 (Horvat 和 Pisanski 2010)。

棱柱图是 优美 的 (Gallian 1987, Frucht 和 Gallian 1988, Gallian 2018)。

对于 n-棱柱图,对于 n=3, 4, ...,有向 哈密顿路径 的数量分别为 60, 144, 260, 456, 700, 1056, 1476, ... (OEIS A124350),它具有漂亮的闭合形式

 |HP(n)|=4n(|_1/2n^2_|+1),

其中 |_x_|向下取整函数 (M. Alekseyev,私人通信,2 月 7 日,2008 年)。

PrismGraphCycles3

对于 n-棱柱图,对于 n=3, 4, ...,图的环 的数量分别为 14, 28, 52, 94, 170, ... (OEIS A077265),如上图所示,对于 n=3

图的笛卡尔积 Y_n square K_2环面网格图 C_4 square K_2 同构。

对于奇数 n,棱柱图 Y_n二部双图 是棱柱图 Y_(2n)

棱柱图的预计算属性在 Wolfram 语言 中可用,如GraphData[{"Prism", n}].

棱柱图推广到 图的笛卡尔积 Y_(m,n)=C_m square P_n 可能被称为 堆叠棱柱图


参见

反棱柱图, 循环图, 交叉棱柱图, 立方图, 环图, 广义 Petersen 图, 轮状图, KC 图, 梯形图, 莫比乌斯梯, 棱柱, 堆叠棱柱图, 网状图

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L. 代数图论,第 2 版。 英国剑桥:剑桥大学出版社,1993 年。Gallian, J. "Labeling Prisms and Prism Related Graphs." Congr. Numer. 59, 89-100, 1987.Gallian, J. "图标记的动态调查。" Elec. J. Combin. DS6. 2018 年 12 月 21 日。 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6Gross, J. T. 和 Yellen, J. 图论及其应用。 Boca Raton, FL: CRC Press, p. 14, 1999.Frucht R. 和 Gallian, J. A. "棱柱的标记。" Ars Combin. 26, 69-82, 1988.Hladnik, M.; Marušič, D.; 和 Pisanski, T. "循环 Haar 图。" Disc. Math. 244, 137-153, 2002.Horvat, B. 和 Pisanski, T. "单位距离图的乘积。" Disc. Math. 310, 1783-1792, 2010.Hosoya, H. 和 Harary, F. "关于三个栅栏图的匹配性质。" J. Math. Chem. 12, 211-218, 1993.Mertens, S. "网格、圆柱体、环面和国王图的支配多项式。" 2024 年 8 月 15 日。 https://arxiv.org/abs/2408.08053Read, R. C. 和 Wilson, R. J. 图谱。 英国牛津:牛津大学出版社,p. 263 和 270, 1998.Sloane, N. J. A. 序列 A077265A124350,在 "整数序列在线百科全书" 中。

在 Wolfram|Alpha 上引用

棱柱图

请引用本文为

Weisstein, Eric W. "棱柱图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PrismGraph.html

主题分类