主題
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 圖, 梯形圖, 莫比烏斯梯, 稜柱, 堆疊稜柱圖, 網狀圖

使用 探索

參考文獻

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,在 "整數序列線上百科全書" 中。

在 上引用

稜柱圖

請引用本文為

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

主題分類