主題
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 圖, 正則圖, 弱正則圖

使用 探索

參考文獻

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.

在 中被引用

強正則圖

引用為

Weisstein, Eric W. "強正則圖。" 來自 —— 資源。 https://mathworld.tw/StronglyRegularGraph.html

主題分類