Movatterモバイル変換

[0]ホーム
URL:

TOPICS
SearchClose
Search

Strongly Regular Graph

DOWNLOAD Mathematica NotebookDownloadWolfram Notebook

Ak-regularsimple graphG onnu nodes is stronglyk-regular if there exist positive integersk,lambda, andmu such that every vertex hask neighbors (i.e., the graph is aregular graph), every adjacent pair of vertices haslambda common neighbors, and every nonadjacent pair hasmu common neighbors (West 2000, pp. 464-465). A graph that is not strongly regular is said to beweakly regular.

Adistance-regular graph withgraph diameterd=2 is a strongly regular graph (Biggs 1993, p. 159). Strongly regular graphs are thereforedistance-regular. Connected strongly regular graphs areconformally rigid (Steinerberger and Thomas 2024).

Thecomplete graphK_n is strongly regular for alln>2. The status of the trivialsingleton graphK_1 is unclear. Opinions differ on ifK_2 is a strongly regular graph, though since it has no well-definedmu parameter, it is preferable to consider itnot to be strongly regular (A. E. Brouwer, pers. comm., Feb. 6, 2013).

Thegraph complement of a non-empty non-complete strongly regular graph with parameters(nu,k,lambda,mu) is another strongly regular graph with parameters(nu,nu-k-1,nu-2-2k+mu,nu-2k+lambda).

A number of strongly regular graphs are implemented in theWolframLanguage asGraphData["StronglyRegular"].

StronglyRegularGraphs

The numbers of strongly regular graphs onnu=1, 2, ... nodes are 1, 1, 2, 4, 3, 6, 2, 6, 5, ... (OEISA076435), the first few of which are illustrated above. The smallestregular graphs that are not strongly regular are thecycle graphC_6 andcirculant graphCi_6(2,3).

StronglyRegularGraphsConnected

Similarly, the numbers of connected strongly regular graphs onnu=1, 2, ... nodes are 1, 0, 1, 2, 2, 3, 1, 3, 3, ... (OEISA088741).

Brouwer (2013) has conjectured that all connected strongly regular graphs (whereK_2 is assumed tonot be strongly regular) areHamiltonian with the exception of thePetersen graph.

StronglyRegularTriangularGraphs

Other than the trivialsingleton graphK_1 and thecomplete bipartite graphsK_(n,n), there are exactly seven known connectedtriangle-free strongly regular graphs, as summarized in the following table (Godsil 1995) and six of which are illustrated above. Determining the existence or absence of any others remains an open problem.

Examples of connected non-complete strongly regular graphs are given in the following table.

(nu,k,lambda,mu)graph
(4,2,0,2)square graph
(5,2,0,1)cycle graphC_5
(6,3,0,3)utility graph
(6,4,2,4)octahedral graph
(8,4,0,4)complete bipartite graphK_(4,4)
(8,6,4,6)16-cell graph
(9,4,1,2)generalized quadrangle GQ(2,1)
(9,6,3,6)complete tripartite graphK_(3,3,3)
(10,3,0,1)Petersen graph
(10,5,0,5)complete bipartite graphK_(5,5)
(10,6,3,4)5-triangular graph
(10,8,6,8)5-cocktail party graph
(12,6,0,6)(6,6)-complete bipartite graphK_(6,6)
(12,8,4,8)(4,4,4)-complete tripartite graphK_(4,4,4)
(12,9,6,9)(3,3,3,3)-complete 4-partite graphK_(3,3,3,3)
(12,10,8,10)6-cocktail party graph
(13,6,2,3)13-Paley graph
(14,7,0,7)complete bipartite graphK_(7,7)
(14,12,10,12)7-cocktail party graph
(15,6,1,3)generalized quadrangle GQ(2,2)
(15,8,4,4)6-triangular graph
(15,10,5,10)complete tripartite graphK_(5,5,5)
(15,12,9,12)complete 5-partite graphK_(3,3,3,3,3)
(16,5,0,2)Clebsch graph
(16,6,2,2)(4,4)-rook graph,Shrikhande graph
(16,8,0,8)complete bipartite graphK_(8,8)
(16,9,4,6)complement of (4,4)-rook graph
(16,10,6,6)5-halved cube graph
(16,12,8,12)complete 4-partite graphK_(4,4,4,4)
(16,14,12,14)8-cocktail party graph
(17,8,3,4)17-Paley graph
(18,9,0,9)complete bipartite graphK_(9,9)
(18,12,6,12)complete tripartite graphK_(6,6,6)
(18,16,14,16)9-cocktail party graph
(20,10,0,10)complete bipartite graphK_(10,10)
(20,18,16,18)10-cocktail party graph
(21,10,3,6)(7,2)-Kneser graph
(21,10,5,4)7-triangular graph
(22,11,0,11)complete bipartite graphK_(11,11)
(22,20,18,20)11-cocktail party graph
(24,12,0,12)complete bipartite graphK_(12,12)
(24,22,20,22)12-cocktail party graph
(25,8,3,2)(5,5)-rook graph
(25,12,5,6)25-Paley graph, 25-Paulus graphs
(26,10,3,4)26-Paulus graphs
(26,13,0,13)complete bipartite graphK_(13,13)
(26,24,22,24)13-cocktail party graph
(27,10,1,5)generalized quadrangle GQ(2,4)
(27,16,10,8)Schläfli graph
(28,12,6,4)8-triangular graph,Chang graphs
(28,14,0,14)complete bipartite graphK_(14,14)
(28,15,6,10)(8,2)-Kneser graph
(28,26,24,26)14-cocktail party graph
(29,14,6,7)(29,14,6,7)-strongly regular graphs, 29-Paley graph
(30,15,0,15)complete bipartite graphK_(15,15)
(30,28,26,28)15-cocktail party graph
(32,16,0,16)complete bipartite graphK_(16,16)
(32,30,28,30)16-cocktail party graph
(34,17,0,17)complete bipartite graphK_(17,17)
(34,32,30,32)17-cocktail party graph
(36,10,4,2)(6,6)-rook graph
(36,14,4,6)U_3(3) graph
(36,14,7,4)9-triangular graph
(36,18,0,18)complete bipartite graphK_(18,18)
(36,21,10,15)(9,2)-Kneser graph
(36,34,32,34)18-cocktail party graph
(37,18,8,9)37-Paley graph
(38,19,0,19)complete bipartite graphK_(19,19)
(38,36,34,36)19-cocktail party graph
(40,20,0,20)complete bipartite graphK_(20,20)
(40,38,36,38)20-cocktail party graph
(41,20,9,10)41-Paley graph
(45,16,8,4)10-triangular graph
(45,28,15,21)(10,2)-Kneser graph
(49,12,5,2)(7,7)-rook graph
(49,24,11,12)49-Paley graph
(50,7,0,1)Hoffman-Singleton graph
(50,42,35,36)Hoffman-Singleton graph complement
(53,26,12,13)53-Paley graph
(55,18,9,4)11-triangular graph
(55,36,21,28)(11,2)-Kneser graph
(56,10,0,2)Gewirtz graph
(61,30,14,15)61-Paley graph
(63,32,16,16)(63,32,16,16)-strongly regular graph
(64,14,6,2)(8,8)-rook graph
(64,21,8,6)64-cyclotomic graph
(66,20,10,4)12-triangular graph
(66,45,28,36)(12,2)-Kneser graph
(73,36,17,18)73-Paley graph
(77,16,0,4)M22 graph
(78,22,11,4)13-triangular graph
(78,55,36,45)(13,2)-Kneser graph
(81,16,7,2)(9,9)-rook graph
(81,20,1,6)Brouwer-Haemers graph
(81,40,19,20)81-Paley graph
(89,44,21,22)89-Paley graph
(91,24,12,4)14-triangular graph
(91,66,45,55)(14,2)-Kneser graph
(97,48,23,24)97-Paley graph
(100,18,8,2)(10,10)-rook graph
(100,22,0,6)Higman-Sims graph
(100,36,14,12)Hall-Janko graph
(101,50,24,25)101-Paley graph
(105,26,13,4)15-triangular graph
(105,78,55,66)(15,2)-Kneser graph
(109,54,26,27)109-Paley graph
(112,30,2,10)generalized quadrangle GQ(3,9)
(113,56,27,28)113-Paley graph
(120,28,14,4)16-triangular graph
(120,56,28,24)(120,56,28,24)-strongly regular graph
(120,63,30,36)(120,63,30,36)-strongly regular graph
(121,60,29,30)121-Paley graph
(125,62,30,31)125-Paley graph
(136,30,15,4)17-triangular graph
(137,68,33,34)137-Paley graph
(149,74,36,37)149-Paley graph
(153,32,16,4)18-triangular graph
(157,78,38,39)157-Paley graph
(162,56,10,24)local McLaughlin graph
(169,84,41,42)169-Paley graph
(171,34,17,4)19-triangular graph
(190,36,18,4)20-triangular graph
(243,22,1,2)Berlekamp-van Lint-Seidel graph
(243,110,37,60)Delsarte graph
(253,112,36,60)(253,112,36,60)-strongly regular graph
(275,112,30,56)McLaughlin graph
(378,52,1,8)5-Cossidente-Penttila graph
(416,100,36,20)G_2(4) graph
(729,112,1,20)Games graph

Strongly regular graphs withlambda=mu correspond to symmetric balanced incomplete block designs (West 2000, p. 465).

See also

Clebsch Graph,Conference Graph,Directed Strongly Regular Graph,Gewirtz Graph,Higman-Sims Graph,Hoffman-Singleton Graph,Regular Graph,Weakly Regular Graph

Explore with Wolfram|Alpha

References

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." InEnumeration 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)."https://www.math.mun.ca/distanceregular/graphs//srg29.14.6.7.html.DistanceRegular.org. "SRG(176,70,18,34)."https://www.math.mun.ca/distanceregular/graphs//srg176.70.18.34.html.DistanceRegular.org. "SRG(176,105,68,54)."https://www.math.mun.ca/distanceregular/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." InSurveys in Combinatorics (Proc. Seventh British Combinatorial Conf., Cambridge, 1979). Cambridge, England: Cambridge University Press, pp. 157-180, 1979.Sloane, N. J. A. SequencesA076435 andA088741 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." InHigher 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.

Referenced on Wolfram|Alpha

Strongly Regular Graph

Cite this as:

Weisstein, Eric W. "Strongly Regular Graph."FromMathWorld--A Wolfram Resource.https://mathworld.wolfram.com/StronglyRegularGraph.html

Subject classifications

Created, developed and nurtured by Eric Weisstein at Wolfram Research
[8]ページ先頭
©2009-2025 Movatter.jp