主题
Search

强正则图


一个 k-正则 简单图 Gnu 个节点上是强 k-正则的,如果存在正整数 klambdamu,使得每个顶点有 k 个邻居(即,该图是一个 正则图),每对相邻顶点有 lambda 个共同邻居,并且每对不相邻顶点有 mu 个共同邻居 (West 2000, pp. 464-465)。一个不是强正则的图被称为 弱正则

一个 距离正则图,其 图直径d=2,是一个强正则图 (Biggs 1993, p. 159)。因此,强正则图是 距离正则 的。连通强正则图是 共形刚性 的 (Steinerberger and Thomas 2024)。

完全图 K_n 对于所有 n>2 都是强正则的。平凡 单点图 K_1 的状态尚不清楚。关于 K_2 是否为强正则图的观点不一,尽管由于它没有明确定义的 mu 参数,最好认为它不是强正则的 (A. E. Brouwer, 私人通信,2 月 6 日,2013 年)。

参数为 (nu,k,lambda,mu) 的非空非完全强正则图的 图的补图 是另一个强正则图,其参数为 (nu,nu-k-1,nu-2-2k+mu,nu-2k+lambda)

许多强正则图在 Wolfram 语言 中实现为GraphData["StronglyRegular"].

StronglyRegularGraphs

节点数为 nu=1, 2, ... 的强正则图的数量分别为 1, 1, 2, 4, 3, 6, 2, 6, 5, ... (OEIS A076435),其中前几个如图所示。不是强正则的最小 正则图环图 C_6循环图 Ci_6(2,3)

StronglyRegularGraphsConnected

类似地,节点数为 nu=1, 2, ... 的连通强正则图的数量分别为 1, 0, 1, 2, 2, 3, 1, 3, 3, ... (OEIS A088741)。

Brouwer (2013) 推测,所有连通强正则图(其中假设 K_2 不是强正则的)都是 哈密顿图,除了 Petersen 图

StronglyRegularTriangularGraphs

除了平凡 单点图 K_1完全二分图 K_(n,n) 之外,恰好有七个已知的连通 无三角形 强正则图,如下表总结(Godsil 1995),其中六个如图所示。确定是否存在任何其他此类图仍然是一个未解决的问题。

下表给出了连通非完全强正则图的示例。

(nu,k,lambda,mu)
(4,2,0,2)方格图
(5,2,0,1)环图 C_5
(6,3,0,3)效用图
(6,4,2,4)八面体图
(8,4,0,4)完全二分图 K_(4,4)
(8,6,4,6)16-胞图
(9,4,1,2)广义四边形 GQ(2,1)
(9,6,3,6)完全三分图 K_(3,3,3)
(10,3,0,1)Petersen 图
(10,5,0,5)完全二分图 K_(5,5)
(10,6,3,4)5-三角形图
(10,8,6,8)5-鸡尾酒会图
(12,6,0,6)(6,6)-完全二分图 K_(6,6)
(12,8,4,8)(4,4,4)-完全三分图 K_(4,4,4)
(12,9,6,9)(3,3,3,3)-完全 4-分图 K_(3,3,3,3)
(12,10,8,10)6-鸡尾酒会图
(13,6,2,3)13-Paley 图
(14,7,0,7)完全二分图 K_(7,7)
(14,12,10,12)7-鸡尾酒会图
(15,6,1,3)广义四边形 GQ(2,2)
(15,8,4,4)6-三角形图
(15,10,5,10)完全三分图 K_(5,5,5)
(15,12,9,12)完全 5-分图 K_(3,3,3,3,3)
(16,5,0,2)Clebsch 图
(16,6,2,2)(4,4)-车图,Shrikhande 图
(16,8,0,8)完全二分图 K_(8,8)
(16,9,4,6)(4,4)-车图的补图
(16,10,6,6)5-半立方体图
(16,12,8,12)完全 4-分图 K_(4,4,4,4)
(16,14,12,14)8-鸡尾酒会图
(17,8,3,4)17-Paley 图
(18,9,0,9)完全二分图 K_(9,9)
(18,12,6,12)完全三分图 K_(6,6,6)
(18,16,14,16)9-鸡尾酒会图
(20,10,0,10)完全二分图 K_(10,10)
(20,18,16,18)10-鸡尾酒会图
(21,10,3,6)(7,2)-Kneser 图
(21,10,5,4)7-三角形图
(22,11,0,11)完全二分图 K_(11,11)
(22,20,18,20)11-鸡尾酒会图
(24,12,0,12)完全二分图 K_(12,12)
(24,22,20,22)12-鸡尾酒会图
(25,8,3,2)(5,5)-车图
(25,12,5,6)25-Paley 图,25-Paulus 图
(26,10,3,4)26-Paulus 图
(26,13,0,13)完全二分图 K_(13,13)
(26,24,22,24)13-鸡尾酒会图
(27,10,1,5)广义四边形 GQ(2,4)
(27,16,10,8)Schläfli 图
(28,12,6,4)8-三角形图,Chang 图
(28,14,0,14)完全二分图 K_(14,14)
(28,15,6,10)(8,2)-Kneser 图
(28,26,24,26)14-鸡尾酒会图
(29,14,6,7)(29,14,6,7)-强正则图,29-Paley 图
(30,15,0,15)完全二分图 K_(15,15)
(30,28,26,28)15-鸡尾酒会图
(32,16,0,16)完全二分图 K_(16,16)
(32,30,28,30)16-鸡尾酒会图
(34,17,0,17)完全二分图 K_(17,17)
(34,32,30,32)17-鸡尾酒会图
(36,10,4,2)(6,6)-车图
(36,14,4,6)U_3(3)
(36,14,7,4)9-三角形图
(36,18,0,18)完全二分图 K_(18,18)
(36,21,10,15)(9,2)-Kneser 图
(36,34,32,34)18-鸡尾酒会图
(37,18,8,9)37-Paley 图
(38,19,0,19)完全二分图 K_(19,19)
(38,36,34,36)19-鸡尾酒会图
(40,20,0,20)完全二分图 K_(20,20)
(40,38,36,38)20-鸡尾酒会图
(41,20,9,10)41-Paley 图
(45,16,8,4)10-三角形图
(45,28,15,21)(10,2)-Kneser 图
(49,12,5,2)(7,7)-车图
(49,24,11,12)49-Paley 图
(50,7,0,1)Hoffman-Singleton 图
(50,42,35,36)Hoffman-Singleton 图 补图
(53,26,12,13)53-Paley 图
(55,18,9,4)11-三角形图
(55,36,21,28)(11,2)-Kneser 图
(56,10,0,2)Gewirtz 图
(61,30,14,15)61-Paley 图
(63,32,16,16)(63,32,16,16)-强正则图
(64,14,6,2)(8,8)-车图
(64,21,8,6)64-分圆图
(66,20,10,4)12-三角形图
(66,45,28,36)(12,2)-Kneser 图
(73,36,17,18)73-Paley 图
(77,16,0,4)M22 图
(78,22,11,4)13-三角形图
(78,55,36,45)(13,2)-Kneser 图
(81,16,7,2)(9,9)-车图
(81,20,1,6)Brouwer-Haemers 图
(81,40,19,20)81-Paley 图
(89,44,21,22)89-Paley 图
(91,24,12,4)14-三角形图
(91,66,45,55)(14,2)-Kneser 图
(97,48,23,24)97-Paley 图
(100,18,8,2)(10,10)-车图
(100,22,0,6)Higman-Sims 图
(100,36,14,12)Hall-Janko 图
(101,50,24,25)101-Paley 图
(105,26,13,4)15-三角形图
(105,78,55,66)(15,2)-Kneser 图
(109,54,26,27)109-Paley 图
(112,30,2,10)广义四边形 GQ(3,9)
(113,56,27,28)113-Paley 图
(120,28,14,4)16-三角形图
(120,56,28,24)(120,56,28,24)-强正则图
(120,63,30,36)(120,63,30,36)-强正则图
(121,60,29,30)121-Paley 图
(125,62,30,31)125-Paley 图
(136,30,15,4)17-三角形图
(137,68,33,34)137-Paley 图
(149,74,36,37)149-Paley 图
(153,32,16,4)18-三角形图
(157,78,38,39)157-Paley 图
(162,56,10,24)局部 McLaughlin 图
(169,84,41,42)169-Paley 图
(171,34,17,4)19-三角形图
(190,36,18,4)20-三角形图
(243,22,1,2)Berlekamp-van Lint-Seidel 图
(243,110,37,60)Delsarte 图
(253,112,36,60)(253,112,36,60)-强正则图
(275,112,30,56)McLaughlin 图
(416,100,36,20)G_2(4)
(729,112,1,20)Games 图

lambda=mu 的强正则图对应于对称平衡不完全区组设计 (West 2000, p. 465)。


另请参阅

Clebsch 图, 会议图, 有向强正则图, Gewirtz 图, Higman-Sims 图, Hoffman-Singleton 图, 正则图, 弱正则图

使用 Wolfram|Alpha 探索

参考文献

Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the Conference on Combinatorics Held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brouwer, A. E. and van Maldeghem, H. Strongly Regular Graphs. Cambridge, England: Cambridge University Press, 2022.Cohen, N. and Pasechnik,  D. V. "Implementing Brouwer's Database of Strongly Regular Graphs." 20 Jul 2016. https://arxiv.org/abs/1601.00181.DistanceRegular.org. "SRG(29,14,6,7) (40 graphs, 20 pairs)." http://www.distanceregular.org/graphs/srg29.14.6.7.html.DistanceRegular.org. "SRG(176,70,18,34)." http://www.distanceregular.org/graphs/srg176.70.18.34.html.DistanceRegular.org. "SRG(176,105,68,54)." http://www.distanceregular.org/graphs/srg176.105.68.54.html.Godsil, C. D. "Triangle-Free Strongly Regular Graphs." Problem 2 in "Problems in Algebraic Combinatorics." Elec. J. Combin. 2, No. F1, pp. 1-20, 1995. http://www.combinatorics.org/Volume_2/Abstracts/v2i1f1.html.McKay, B. "Strongly Regular Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Royle, G. "Strongly Regular Graphs." http://school.maths.uwa.edu.au/~gordon/remote/srgs/.Seidel, J. J. "Strongly Regular Graphs." In Surveys in Combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979). Cambridge, England: Cambridge University Press, pp. 157-180, 1979.Sloane, N. J. A. Sequences A076435 and A088741 in "The On-Line Encyclopedia of Integer Sequences."Spence, E. "Strongly Regular Graphs on at Most 64 Vertices." http://www.maths.gla.ac.uk/~es/srgraphs.html.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." 19 Feb 2024. https://arxiv.org/abs/2402.11758.Thas, J. A. "Combinatorics of Partial Geometries and Generalized Quadrangles." In Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976). Dordrecht, Netherlands: Reidel, pp. 183-199, 1977.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

在 Wolfram|Alpha 中被引用

强正则图

引用为

Weisstein, Eric W. "强正则图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/StronglyRegularGraph.html

主题分类