主题
Search

十二面体图

下载 Mathematica 笔记本下载 Wolfram 笔记本
DodecahedralGraphEmbeddings

十二面体图是对应于十二面体顶点连通性的柏拉图图，如上图在四种嵌入方式中所示。左侧的嵌入显示了十二面体的球面投影，第二个是正交投影，第三个来自 Read 和 Wilson (1998, p. 162)，第四个源自LCF 记号。

十二面体图是大星形十二面体以及十二面体的骨架。

它是三次对称图，表示为 F_(020)A，并且与广义 Petersen 图 GP(10,2) 同构。它可以用 LCF 记号描述为 [10, 7, 4, -4, -7, 10, -4, 7, -7, 4]^2。

十二面体图在 Wolfram 语言 中实现为GraphData["DodecahedralGraph"].

它是距离正则的，具有相交数组 {3,2,1,1,1;1,1,1,2,3}，并且也是距离传递的。

DodecahedralGraphUnitDistance

它也是一个单位距离图 (Gerbracht 2008)，如上图在单位距离嵌入中所示。

在这个图上找到哈密顿环被称为二十面体游戏。十二面体图不是哈密顿连通的，并且是唯一已知的顶点传递哈密顿图（除了圈图 C_n）不是 H-*-连通的 (Stan Wagon，私人通信，2013 年 5 月 20 日)。

十二面体图有 20 个节点，30 条边，顶点连通度 3，边连通度 3，图直径 5，图半径 5，和围长 5。它的色数为 3。它的图谱是 Spec(G)=(-sqrt(5))^3(-2)^40^41^5(sqrt(5))^33^1 (Buekenhout 和 Parker 1998; Cvetkovic et al. 1998, p. 308)。它的自同构群的阶数为 |Aut(G)|=120 (Buekenhout 和 Parker 1998)。

DodecahedralGraphMinimalPlanarIntegralDrawing

十二面体图的最小平面整数嵌入的最大边长为 2 (Harborth et al. 1987)。它也是优美的 (Gardner 1983, pp. 158 and 163-164; Gallian 2018, p. 35; Knuth 2024)，具有 784298856 种基本不同的标记，总共有 2×120×784298856=188231725440 种优美标记 (B. Dobbelaere，私人通信，2020 年 10 月 22 日)，这个数字由 T. Rokicki 在 2020 年 10 月 6 日独立（并且几乎同时！）确定 (D. Knuth，私人通信，2023 年 7 月 6 日)。

十二面体图可以构造为 10P_2 的图扩展，步长为 1 和 2，其中 P_2 是一个路径图 (Biggs 1993, p. 119)。

大星形十二面体的骨架与十二面体图同构。

十二面体图的线图是二十-十二面体图。十二面体图的图平方是交叉十二面体图。

十二面体图具有色多项式

pi(z)=(z-2)(z-1)z(z^(17)-27z^(16)+352z^(15)-2950z^(14)+17839z^(13)-82777z^(12)+305866z^(11)-921448z^(10)+2297495z^9-4783425z^8+8347700z^7-12195590z^6+14808795z^5-14713381z^4+11613602z^3-6892084z^2+2751604z-555984).
DodecahedralGraphMatrices

上面的图显示了十二面体图的邻接矩阵、关联矩阵和图距离矩阵。

十二面体图的二部双图是三次对称图 F_(040)A。

下表总结了十二面体图的属性。

属性值
自同构群阶数120
特征多项式(x-3)(x-1)^5x^4(x+2)^4(x^2-5)^3
色数3
色多项式pi(x)
无爪的否
团数2
由谱确定是
直径5
距离正则图是
对偶图名称二十面体图
边色数3
边连通度3
边数30
欧拉图否
广义 Petersen 指数(10,2)
围长5
哈密顿图是
哈密顿环计数60
哈密顿路径计数?
积分图否
独立数8
LCF 记号[-10,-4,7,-7,4,-10,7,4,-4,-7]^2
线图?
线图名称二十-十二面体图
完美匹配图否
平面图是
多面体图是
多面体嵌入名称十二面体, 大星形十二面体
半径5
正则图是
谱(-sqrt(5))^3(-2)^40^41^5(sqrt(5))^33^1
无平方图是
可追踪图是
无三角形图是
顶点连通度3
顶点数20
弱正则参数(20,3,0,0,1)

另请参阅

三次对称图, 立方图, Grünbaum 图, 二十面体图, 二十面体游戏, 八面体图, 柏拉图图, 四面体图

使用 探索

参考文献

Ball, W. W. R. 和 Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987.Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, 1976.Buekenhout, F. 和 Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension <=4." Disc. Math. 186, 69-94, 1998.Chartrand, G. Introductory Graph Theory. New York: Dover, 1985.Cvetković, D. M.; Doob, M.; 和 Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.DistanceRegular.org. "Dodecahedron." http://www.distanceregular.org/graphs/dodecahedron.html.Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Harborth, H. 和 Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.Harborth, H.; Kemnitz, A.; Möller, M.; 和 Süssenbach, A. "Ganzzahlige planare Darstellungen der platonischen Körper." Elem. Math. 42, 118-122, 1987.Knuth, D. E. Problem 101 in §7.2.2.3 in The Art of Computer Programming, Vol. 4. Pre-Fascicle 7A, Dec. 5, pp. 122 和 181-192, 2024.Read, R. C. 和 Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 266, 1998.Royle, G. "F020A." http://www.csse.uwa.edu.au/~gordon/foster/F020A.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 198, 1990.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

请引用本文为

Weisstein, Eric W. "Dodecahedral Graph." 来自 MathWorld-- 资源。 https://mathworld.net.cn/DodecahedralGraph.html

学科分类