主題
Search

廣義彼得森圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
GeneralizedPetersenGraphs

廣義彼得森圖 GP(n,k), 也記作 P(n,k) (Biggs 1993, p. 119; Pemmaraju and Skiena 2003, p. 215), 對於 n>=3 和 1<=k<=|_(n-1)/2_| 是一個連通 三次圖，由一個內部星形多邊形 {n,k} (迴圈圖 Ci_n(k)) 和一個外部正多邊形 {n} (圈圖 C_n) 組成，內部和外部多邊形中對應的頂點透過邊連線。這些圖由 Coxeter (1950) 引入，並由 Watkins (1969) 命名。它們不應與七個彼得森族圖混淆。

由於廣義彼得森圖是三次圖，m/n=3/2，其中 m 是邊數，n 是頂點數。更具體地說，GP(n,k) 有 2n 個節點和 3n 條邊。

廣義彼得森圖在 Wolfram 語言 中實現為PetersenGraph[k, n]，它們的屬性可以使用GraphData[{"GeneralizedPetersen", {k, n}}].

廣義彼得森圖可以進一步推廣到 I 圖。

對於奇數 n, GP(n,k) 同構於 GP(n,(n-2k+3)/2)。因此，例如，GP(7,2)=GP(7,3), GP(9,2)=GP(9,4), GP(11,2)=GP(11,5), GP(11,3)=GP(11,4), 等等。節點數為 n=6, 8, ... 的非同構廣義彼得森圖的數量為 1, 1, 2, 2, 2, 3, 3, 4, 3, 5, 4, 5, 6, 6, 5, 7, ... (OEIS A077105)。

GP(n,k) 是頂點傳遞的當且僅當 k^2=+/-1 (mod n) 或 (n,k)=(10,2), 並且是對稱的僅在以下情況下：(n,k)=(4,1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), 和 (24, 5) (Frucht et al. 1971; Biggs 1993, p. 119)。

Tutte 證明了 GP(9,4) 具有唯一的 3-邊著色。

GP(12,5) 是 Nauru 圖 F_(024)A 並且具有 LCF 符號 [5,-9,7,-7,9,-5]^4 (Frucht 1976)。

所有廣義彼得森圖都是單位距離圖 (Žitnik et al. 2010)。然而，透過扭曲成為單位距離的廣義彼得森指標（其中一些對應於同一圖）僅對應於 (n,k)=(5,2), (6, 2), (7, 2), (7, 3), (8, 2), (8, 3), (9, 2), (9, 3), (9, 4), (10, 2), (10, 3), (11, 2), (12, 2) (Žitnik et al. 2010)。

廣義彼得森圖 GP(n,k) 是非哈密頓圖的當且僅當 k=2 且 n=5 (mod 6) (Alspach 1983; Holton and Sheehan 1993, p. 316)。此外，GP(n,2) 對於 n>=3 的哈密頓環的數量由下式給出

{2F_(n/2+2)-2F_(n/2-2)-2 for n=0,2 (mod 6); n for n=1 (mod 6); 3 for n=3 (mod 6); n+2F_(n/2+2)-2F_(n/2-2)-2 for n=4 (mod 6); 0 for n=5 (mod 6)
(1)

(Schwenk 1989; Holton and Sheehan 1993, p. 316)。

下表給出了一些廣義彼得森圖的特殊情況。

圖廣義彼得森圖
三次對稱圖 F_(048)AGP(24,5)
立方圖GP(4,1)
Desargues 圖GP(10,3)
十二面體圖GP(10,2)
Dürer 圖GP(6,2)
Möbius-Kantor 圖GP(8,3)
Nauru 圖GP(12,5)
Petersen 圖GP(5,2)
稜柱圖GP(n,1)

另請參閱

I 圖, Petersen 圖

使用 探索

參考文獻

Alspach, B. R. "哈密頓廣義彼得森圖的分類." J. Combin. Th. Ser. B 34, 293-312, 1983.Biggs, N. L. 代數圖論，第二版 Cambridge, England: Cambridge University Press, 1993.Bondy, J. A. "哈密頓主題的變體." Canad. Math. Bull. 15, 57-62, 1972.Coxeter, H. S. M. "自對偶配置和正則圖." Bull. Amer. Math. Soc. 56, 413-455, 1950.Fiorini, S. "廣義彼得森圖的交叉數." Combinatorics '84. Amsterdam, Netherlands: North Holland Press.Frucht, R. "三價哈密頓圖的規範表示." J. Graph Th. 1, 45-60, 1976.Frucht, R.; Graver, J. E.; 和 Watkins, M. E. "廣義彼得森圖的群." Proc. Cambridge Philos. Soc. 70, 211-218, 1971.Holton, D. A. 和 Sheehan, J. "廣義彼得森圖和置換圖." §9.13 in 彼得森圖。 Cambridge, England: Cambridge University Press, pp. 45 和 315-317, 1993.Lovrečič Saražin, M. "關於也是 Cayley 圖的廣義彼得森圖的註記." J. Combin. Th. B 69, 226-229, 1997.Pemmaraju, S. 和 Skiena, S. 計算離散數學：組合數學與圖論（使用 Mathematica）。 Cambridge, England: Cambridge University Press, 2003.Read, R. C. 和 Wilson, R. J. 圖集。 Oxford, England: Oxford University Press, p. 275, 1998.Schrag, G. 和 Cammack, L. "關於廣義彼得森圖的 2-可擴充套件性." Disc. Math. 78, 169-177, 1989.Schwenk, A. "某些廣義彼得森圖中的哈密頓環的列舉." J. Combin. Th. Ser. B 47, 53-59, 1989.Sloane, N. J. A. 序列 A077105 in "整數序列線上百科全書."Watkins, M. E. "關於 Tait 著色定理及其在廣義彼得森圖中的應用." J. Combin. Th. 6, 152-164, 1969.Žitnik, A.; Horvat, B.; 和 Pisanski, T. "所有廣義彼得森圖都是單位距離圖." J. Korean Math. Soc. 49, 475-491, 2012.

在 中引用

廣義彼得森圖

請這樣引用

Weisstein, Eric W. "廣義彼得森圖。" 來自 Web 資源。 https://mathworld.tw/GeneralizedPetersenGraph.html

主題分類