主題
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." 來自 Web 資源。 https://mathworld.tw/DodecahedralGraph.html

學科分類