主題
Search

穆爾圖


MooreGraphs

型別為 (v,g) 的穆爾圖是一個正則圖,其頂點度v>2圍長g,它包含最大可能數量的節點,即

 n(v,g)={1+(v-1)^(g/2-1)+vsum_(r=0)^((g-4)/2)(v-1)^r   for g even; 1+vsum_(r=0)^((g-3)/2)(v-1)^r   for g odd
(1)

(Bannai 和 Ito 1973; Royle)。

等價地,它是一個 (v,g)-籠狀圖,其中 v 是頂點度,g圍長,且過剩度為零 (Wong 1982)。穆爾圖也稱為最小 (v,g)-圖 (Wong 1982),並且總是距離正則的。

節點數為 n=1, 2, ... 的穆爾圖的數量為 0, 0, 0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, ...。下表列出了一些穆爾圖(不包括完全圖和完全二部圖)。

(v,g)命名的穆爾圖(或參考文獻)
(3,5)Petersen 圖
(3,6)Heawood 圖
(3,8)Tutte 8-籠狀圖
(4,6)Wong (1982)
(5,6)4 階廣義三角形
(7,5)Hoffman-Singleton 圖

Hoffman 和 Singleton (1960) 在研究給定頂點度 v直徑 d 的相關正則 (v,d) 圖時,首次使用了術語“穆爾圖”。他們表明,對於型別 (v,d)=(3,2) (Petersen 圖) 和 (7,2) (Hoffman-Singleton 圖),存在唯一的穆爾圖,其中 d圖直徑,但沒有其他 (v,d=2) 直徑為 2 的穆爾圖,可能的例外是 (57,d=2) (Bannai 和 Ito 1973)。Bannai 和 Ito (1973) 隨後表明,不存在圍長 g>=4 且價 v>2 的型別為 (v,g) 的穆爾圖。等價地,(v,g)-穆爾圖僅在以下情況下存在:(1) g=5v=3, 7, 或(可能)57,或 (2) g=6, 8, 或 12 (Wong 1982)。這解決了有限穆爾圖的存在性和唯一性問題,但 (57,2) 情況除外,這種情況仍然是開放問題。這個定理的證明,有時被稱為Hoffman-Singleton 定理,是困難的 (Hoffman 和 Singleton 1960, Feit 和 Higman 1964, Damerell 1973, Bannai 和 Ito 1973),但可以在 Biggs (1993) 中找到。


另請參閱

籠狀圖, 度-直徑問題, 距離正則圖, 廣義穆爾圖, 廣義多邊形, 圍長, Heawood 圖, Hoffman-Singleton 圖, Hoffman-Singleton 定理, Petersen 圖, 正則圖, Tutte 8-籠狀圖

使用 探索

參考文獻

Aschbacher, M. "The Non-Existence of Rank Three Permutation Group of Degree 3250 and Subdegree 57." J. Algebra 19, 538-540, 1971.Bannai, E. and Ito, T. "On Moore Graphs." J. Fac. Sci. Univ. Tokyo Ser. A 20, 191-208, 1973.Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Bosák, J. "Cubic Moore Graphs." Mat. Časopis Sloven. Akad. Vied 20, 72-80, 1970.Bosák, J. "Partially Directed Moore Graphs." Math. Slovaca 29, 181-196, 1979.Damerell, R. M. "On Moore Graphs." Proc. Cambridge Philos. Soc. 74, 227-236, 1973.Feit, W. and Higman, G. "The Non-Existence of Certain Generalized Polygons." J. Algebra 1, 114-131, 1964.Friedman, H. D. "On the Impossibility of Certain Moore graphs." J. Combin. Th. B 10, 245-252, 1971.Godsil, C. D. "Problems in Algebraic Combinatorics." Electronic J. Combinatorics 2, No. 1, F1, 1-20, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1f1.html.Godsil, C. and Royle, G. "Moore Graphs." §5.8 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 90-91, 2001.Hoffman, A. J. and Singleton, R. R. "On Moore Graphs of Diameter 2 and 3." IBM J. Res. Develop. 4, 497-504, 1960.Royle, G. "Cages of Higher Valency." http://www.csse.uwa.edu.au/~gordon/cages/allcages.html.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

在 中被引用

穆爾圖

引用為

Weisstein, Eric W. "穆爾圖。" 來自 網路資源。 https://mathworld.tw/MooreGraph.html

主題分類