主題
Search

希伍德圖


HeawoodGraphEmbeddings

希伍德圖是一個具有 14 個頂點和 21 條邊的三次圖,它是唯一的 (3,6)-籠形圖。它也是一個摩爾圖。它的圖直徑為 3,圖半徑為 3,圍長為 6。它是三次對稱的,非平面的,哈密頓的,並且可以用 LCF 符號表示為 [5,-5]^7。上面展示了希伍德圖的幾種嵌入方式。

希伍德圖同構於廣義六邊形 GH(1,2)克諾德爾圖 W_(3,14)蜂巢環面圖 HTG(1,14,5)線圖廣義六邊形 GH(2,1)

它的色數為 2,色多項式

 pi_G(z)=z(z-1)(z^(12)-20z^(11)+190z^(10)-1140z^9+4845z^8-15476z^7+38340z^6-74587z^5+113433z^4-131700z^3+110794z^2-60524z+16161).

它的圖譜(-3)^1(-sqrt(2))^6(sqrt(2))^63^1

它是 4-傳遞的,但不是 5-傳遞的 (Harary 1994, p. 173)。

希伍德圖是 14 個節點上八個三次圖之一,其最小可能的圖交叉數為 3(另一個是廣義 Petersen 圖 GP(7,2)),這使其成為最小三次交叉數圖 (Pegg and Exoo 2009, Clancy et al. 2019)。

HeawoodTorusColoring

希伍德圖對應於上面展示的 14 個節點上的七色環面地圖。希伍德圖是 Fano 平面上的點/線 Levi 圖 (Royle)。

HeawoodGraphUnitDistance

Chvátal (1972) 推測,有限射影平面的點-線關聯圖(其中最小的例子是希伍德圖)不是單位距離可嵌入的。Gerbracht (2008) 發現了第一個明確的反駁此猜想的嵌入,Gerbracht (2009) 按照 Harris (2007) 首先提出的通用概要,發表了正好 11 個這樣的嵌入(如上所示)。

HeawoodGraphUnitDistanceHexagon

E. Gerbracht (私人通訊,2010 年 1 月) 也構建了一個基於中心六邊形的明顯的單位距離嵌入。

HeawoodGraphUnitDistanceHorvat

Horvat (2009) 顯然也找到了另一個單位距離嵌入,如上所示。

希伍德圖是 Harary (1994) 封面描繪的四個圖中的第二個。

它在 Wolfram 語言中實現為GraphData["HeawoodGraph"].


另請參閱

籠形圖, Fano 平面, Foster 圖, 希伍德四色圖, 蜂巢環面圖, 摩爾圖, 最小三次交叉數圖, Szilassi 多面體, 環面著色

使用 探索

參考文獻

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236 and 244, 1976.Brouwer, A. E. "Heawood Graph." http://www.win.tue.nl/~aeb/drg/graphs/Heawood.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 209 and 221, 1989.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European J. Combin. 14, 397-407, 1993.Chvátal, V. Problem 21 in Chvátal, V.; Klarner, D. E.; and Knuth, D. E. "Selected Combinatorial Research Problems." Tech. Report STAN-CS-72-292, Computer Science Department, School of Humanities and Sciences. Stanford, CA: Stanford University, pp. 11-13, 1972.Clancy, K.; Haythorpe, M.; Newcombe, A.; and Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.DistanceRegular.org. "Heawood Graph = Incidence Graph of PG(2,2) = Incidence Graph of Hadamard (7,3,1)-Design." http://www.distanceregular.org/graphs/heawood.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Heawood Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/heawood.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Gerbracht, E. H.-A. "Eleven Unit Distance Embeddings of the Heawood Graph." Dec. 30, 2009. http://arxiv.org/abs/0912.5395.Gethner, E. and Springer, W. M. II. "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164, 159-175, 2003.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 173, 1994.Harris, M. A. "Toward a Unit Distance Embedding for the Heawood Graph." Nov. 7, 2007. http://arxiv.org/abs/math/0711.1157.Heawood, P. J. "Map-Colour Theorem." Quart. J. Math. Oxford Ser. 24, 332-338, 1890.Horvat, B. "Predstavitve grafov z enotsko razdaljo" ("Representations of Unit-Distance Graphs"). Ph.D. thesis, Faculty of Computer and Information Science. Ljubljana, Slovenia: University of Ljubljana, June 2009. http://eprints.fri.uni-lj.si/858/.Pegg, E. Jr. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 271, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Royle, G. "F014A." http://www.csse.uwa.edu.au/~gordon/foster/F014A.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.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. "希伍德圖。" 來自 Web 資源。 https://mathworld.tw/HeawoodGraph.html

主題分類