主题
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 图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中引用

广义彼得森图

请这样引用

Weisstein, Eric W. "广义彼得森图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GeneralizedPetersenGraph.html

主题分类