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

主题分类