主题
Search

McGee图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
McGeeGraphConstruction

McGee图是一个 三次对称图，具有 24 个节点和 36 条边，它是唯一的 7-笼状图。它可以构造为上面所示的最左边两个子图的并集（Harary 1994，第 174 页）。它由 H. Sachs（未发表；参见 Kárteszi 1960）和 McGee (1960) 发现，并由 Tutte (1966；Wong 1982，Brouwer等人 1989，第 209 页) 证明是唯一的。它的围长为 7，直径为 4，色数为 3。

McGeeGraph2

上面展示了一个对称嵌入。

McGeeGraph

McGee图是哈密顿图，并且具有一个阶数为 8 的独特 LCF 表示法，[-12,7,-7]^8，一个阶数为 2 的表示法和两个阶数为 1 的表示法，所有这些都在上面展示。

它的自同构群的大小为 32，并且它具有图谱

1/2(-1-sqrt(17))alpha^4(-2)(-1)^2beta^40^31/2(-1+sqrt(17))gamma^42^33,

其中 alpha, beta, 和 gamma 是 x^3+x^2-4x-2 的根。

McGeeGraphCrossings

McGee图的直线交叉数是 8，由 G. Exoo 在 1990 年左右确定（G. Exoo，私人通讯，2019 年 5 月 12 日）。它是 24 个节点上直线交叉数最小（为 8）的三个三次图之一（另一个是瑙鲁图），使其成为最小三次交叉数图（Pegg 和 Exoo 2009，Clancy等人 2019）。

该图不是顶点传递的（Holton 和 Sheehan 1993，第 207-208 页），因为它的自同构群具有长度为 8 和 16 的轨道。因此，它也不是 4-传递的（正如 Harary 1994，第 175 页错误地陈述的那样）。

它在 Wolfram 语言中实现为GraphData["McGeeGraph"].

另请参阅

笼状图, 三次对称图, 瑙鲁图, 最小三次交叉数图

使用 探索

参考文献

Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 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.Exoo, G. "Rectilinear Drawings of Famous Graphs: The McGee Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/mcgee.gif.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Holton, D. A. 和 Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Kárteszi, F. "Piani finit ciclici come risoluzioni di un certo problemo di minimo." Boll. Un. Mat. Ital. 15, 522-528, 1960.McGee, W. F. "A Minimal Cubic Graph of Girth Seven." Canad. Math. Bull. 3, 149-152, 1960.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.Read, R. C. 和 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/.Tutte, W. T. Connectivity in Graphs. Toronto, Ontario: University of Toronto Press, 1966.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

引用为

Weisstein, Eric W. “McGee 图。” 来自 Web 资源。 https://mathworld.net.cn/McGeeGraph.html

主题分类