Petersen 图是具有 10 个顶点和 15 条边的三次图，它是唯一的 
-笼形图 (Harary 1994, p. 175)，以及唯一的 
-穆尔图。它可以构造为 
以步长 1 和 2 的图展开，其中 
是一个 路径图 (Biggs 1993, p. 119)。切除 Petersen 图的一条边会得到 4-莫比乌斯梯子 
。上面在几个嵌入中说明了它 (D'Angelo and Saaty and Kainen 1986; Harary 1994, p. 89; West 2000, p. 229; Knuth 2008, p. 39)。Petersen 图也是 10-Lindgren-Sousselier 图。
该图由 Petersen (1898) 引入，作为边着色问题的一个反例。然而，Kempe (1886) 早在十二年前就将其描述为顶点对应于 Desargues 配置 的点，边对应于不位于配置线的点对的图。以这种方式从配置产生的图已被 Ed Pegg, Jr. 称为普通（线）图。（私人通讯，2024 年 9 月 11 日）。
Petersen 图可以推广，得到的图被称为 广义 Petersen 图 
，对于 
和 
。Petersen 图对应于 
。
Petersen 图的围长为 5，直径为 2，边色数 为 4，色数 为 3，色多项式 为
Petersen 图是一个 三次对称图，并且是非平面的。以下 D. West 的优美证明论证了 Petersen 图是非哈密顿的。如果存在 10-圈 
，则该图由 
加上五条弦组成。如果每条弦连接 
上相对的顶点，则存在 4-圈。因此，某条弦 
连接 
上距离为 4 的顶点。现在，没有弦与 
在 
上的端点的相对顶点关联，可以在不创建最多四个顶点的圈的情况下添加。因此，Petersen 图是非哈密顿的。事实上，它也是最小的次哈密顿图。
Petersen 图是两个在 10 个节点上具有最小可能图交叉数 2 的三次图之一（另一个是由 Pegg 和 Exoo 2009 表示的未命名图 CNG 2B），使其成为最小三次交叉数图 (Pegg 和 Exoo 2009, Clancy et al. 2019)。
Petersen 图是在 10 个顶点上的唯一几乎哈密顿三次图 (Punnim et al. 2007)。事实上，它也是最大非哈密顿的 (Clark 和 Entringer 1983)。
它也是一个单位距离图 (Gerbracht 2008)。
Petersen 图是唯一没有 Tait 着色的最小围长图。它是完全图 
的线图的补图 (Skiena 1990, p. 139)，以及奇图 
(Skiena 1990, p. 162)。
Petersen 图是一个积分图，其图谱为 
。
Petersen 图的二分双图是Desargues 图。
Petersen 图的线图是四次顶点传递图 Qt39，如上所示在几个嵌入中说明。
Petersen 图被描绘在期刊 Journal of Graph Theory 和 Discrete Mathematics 的封面上。它也是 Harary (1994) 封面右下角的图。
Petersen 图提供了射影平面的 6 着色。
Petersen 图在 Wolfram 语言中实现为PetersenGraph[]，许多预计算属性可通过以下方式获得GraphData["PetersenGraph"].
下表总结了 Petersen 图的一些属性。
| 属性 | 值 |
| 自同构群阶 | 120 |
| 特征多项式 |  |
| 色数 | 3 |
| 无爪图 | 否 |
| 团数 | 2 |
| 图补图名称 | 5-三角形图 |
| 直径 | 2 |
| 距离正则图 | 是 |
| 边色数 | 4 |
| 边连通度 | 3 |
| 边数 | 15 |
| 边传递 | 是 |
| 欧拉图 | 否 |
| 围长 | 5 |
| 哈密顿图 | 否 |
| 哈密顿圈计数 | 0 |
| 哈密顿路径计数 | 240 |
| 次哈密顿图 | 是 |
| 次可追踪图 | 否 |
| 积分图 | 是 |
| 独立数 | 4 |
| 线图 | 否 |
| 线图名称 | 四次顶点传递图 Qt39 |
| 完美图 | 否 |
| 完美匹配图 | 是 |
| 平面图 | 否 |
| 多面体图 | 否 |
| 半径 | 2 |
| 正则图 | 是 |
| 无平方图 | 是 |
| 强正则图 |  |
| 对称图 | 是 |
| 可追踪图 | 是 |
| 无三角形图 | 是 |
| 顶点连通度 | 3 |
| 顶点数 | 10 |
| 顶点传递 | 是 |
参见
笼形图,
广义 Petersen 图,
围长,
Hoffman-Singleton 图,
次哈密顿图,
积分图,
克内泽图,
Lindgren-Sousselier 图,
穆尔图,
奇图,
Petersen 图族,
最小三次交叉数图
使用 Wolfram|Alpha 探索
参考文献
Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236 和 243, 1976.Brouwer, A. E. "Petersen Graph." http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 104 和 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; 和 Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Clark, L. 和 Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.D'Angelo, J. P. 和 West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.DistanceRegular.org. "Petersen Graph 
." http://www.distanceregular.org/graphs/petersen.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Petersen Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/pete.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 89, 112, and 175, 1994.Hoffman, A. J. 和 Singleton, R. R. "On Moore Graphs of Diameter Two and Three." IBM J. Res. Develop. 4, 497-504, 1960.Holton, D. A. 和 Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Horvat, B. 和 Pisanski, T. "Unit Distance Representations of the Petersen Graph in the Plane." To appear in Ars Combin..Kempe, A. B. "A Memoir on the Theory of Mathematical Form." Philos. Trans. Royal Soc. London 177, 1-70, 1886.Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, 2008.Nedela, R. 和 Škoviera, M. "Which Generalized Petersen Graphs Are Cayley Graphs?" J. Graph Th. 19, 1-11, 1995.Pegg, E. Jr. 和 Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Petersen, J. "Sur la théorème de Tait." L'Intermédiare des Math. 5, 225-227, 1898.Punnim, N.; Saenpholphat, V.; 和 Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Read, R. C. 和 Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 271 和 276, 1998.Royle, G. "F010A." http://www.csse.uwa.edu.au/~gordon/foster/F010A.html.Saaty, T. L. 和 Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 102, 1986.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 139, 162, and 191, 1990.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, pp. 90-91, 2008.Steimle, A. 和 Staton, W. "The Isomorphism Classes of the Generalized Petersen Graphs." Disc. Math. 309, 231-237, 2009.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.
请引用本文为
Weisstein, Eric W. "Petersen 图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/PetersenGraph.html
学科分类
