主題
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.tw/McGeeGraph.html

主題分類