主题
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.net.cn/HeawoodGraph.html

主题分类