Strongly regular graph

Short description: Concept in graph theory

The Paley graph of order 13, a strongly regular graph with parameters (13,6,2,3). Graph families defined by their automorphisms

distance-transitive | -> | distance-regular | <- | strongly regular
↓ |  |
symmetric (arc-transitive) | <- | t-transitive, t ≥ 2 |  | skew-symmetric
↓ |  |  |  |
(if connected)
vertex- and edge-transitive | -> | edge-transitive and regular | -> | edge-transitive
↓ |  | ↓ |  | ↓
vertex-transitive | -> | regular | -> | (if bipartite)
biregular
↑ |  |
Cayley graph | <- | zero-symmetric |  | asymmetric

In graph theory, a strongly regular graph (SRG) is a regular graph G = (V, E) with v vertices and degree k such that for some given integers λ,μ≥0

* every two adjacent vertices have λ common neighbours, and
* every two non-adjacent vertices have μ common neighbours.

Such a strongly regular graph is denoted by srg(v, k, λ, μ). Its complement graph is also strongly regular: it is an srg(v, v − k − 1, v − 2 − 2k \+ μ, v − 2k \+ λ).

If a graph G is strongly regular with μ > 0, then G is distance-regular with diameter 2. Likewise, if G is strongly regular with λ = 1, then it is locally linear.

## Contents

* 1 Etymology
* 2 History
* 3 Examples
* 3.1 Triangle-free graphs
* 3.2 Geodetic graphs
* 4 Algebraic properties of strongly regular graphs
* 4.1 Basic relationship between parameters
* 4.2 Adjacency matrix equations
* 4.3 Eigenvalues and graph spectrum
* 4.4 The Hoffman–Singleton theorem
* 5 See also
* 6 Notes
* 7 References
* 8 External links

## Etymology

A strongly regular graph is denoted as an srg(v, k, λ, μ) in the literature. By convention, graphs which satisfy the definition trivially are excluded from detailed studies and lists of strongly regular graphs. These include the disjoint union of one or more equal-sized complete graphs,[1][2] and their complements, the complete multipartite graphs with equal-sized independent sets.

Andries Brouwer and Hendrik van Maldeghem (see #References) use an alternate but fully equivalent definition of a strongly regular graph based on spectral graph theory: a strongly regular graph is a finite regular graph that has exactly three eigenvalues, only one of which is equal to the degree k, of multiplicity 1. This automatically rules out fully connected graphs (which have only two distinct eigenvalues, not three) and disconnected graphs (for which the multiplicity of the degree k is equal to the number of different connected components, which would therefore exceed one). Much of the literature, including Brouwer, refers to the larger eigenvalue as r (with multiplicity f) and the smaller one as s (with multiplicity g).

## History

Strongly regular graphs were introduced by R.C. Bose in 1963.[3] They built upon earlier work in the 1950s in the then-new field of spectral graph theory.

## Examples

* The cycle of length 5 is an srg(5, 2, 0, 1).
* The Petersen graph is an srg(10, 3, 0, 1).
* The Clebsch graph is an srg(16, 5, 0, 2).
* The Shrikhande graph is an srg(16, 6, 2, 2) which is not a distance-transitive graph.
* The n × n square rook's graph, i.e., the line graph of a balanced complete bipartite graph Kn,n, is an srg(n2, 2n − 2, n − 2, 2). The parameters for n = 4 coincide with those of the Shrikhande graph, but the two graphs are not isomorphic. (The vertex neighborhood for the Shrikhande graph is a hexagon, while that for the rook graph is two triangles.)
* The line graph of a complete graph Kn is an srg⁡((n2),2(n−2),n−2,4).
* The three Chang graphs are srg(28, 12, 6, 4), the same as the line graph of K8, but these four graphs are not isomorphic.
* Every generalized quadrangle of order (s, t) gives an srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) as its line graph. For example, GQ(2, 4) gives srg(27, 10, 1, 5) as its line graph.
* The Schläfli graph is an srg(27, 16, 10, 8) and is the complement of the aforementioned line graph on GQ(2, 4).[4]
* The Hoffman–Singleton graph is an srg(50, 7, 0, 1).
* The Gewirtz graph is an srg(56, 10, 0, 2).
* The M22 graph aka the Mesner graph is an srg(77, 16, 0, 4).
* The Brouwer–Haemers graph is an srg(81, 20, 1, 6).
* The Higman–Sims graph is an srg(100, 22, 0, 6).
* The Local McLaughlin graph is an srg(162, 56, 10, 24).
* The Cameron graph is an srg(231, 30, 9, 3).
* The Berlekamp–van Lint–Seidel graph is an srg(243, 22, 1, 2).
* The McLaughlin graph is an srg(275, 112, 30, 56).
* The Paley graph of order q is an srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4). The smallest Paley graph, with q = 5, is the 5-cycle (above).
* Self-complementary arc-transitive graphs are strongly regular.

A strongly regular graph is called primitive if both the graph and its complement are connected. All the above graphs are primitive, as otherwise μ = 0 or v \+ λ = 2k.

Conway's 99-graph problem asks for the construction of an srg(99, 14, 1, 2). It is unknown whether a graph with these parameters exists, and John Horton Conway offered a $1000 prize for the solution to this problem.[5]

### Triangle-free graphs

The strongly regular graphs with λ = 0 are triangle free. Apart from the complete graphs on fewer than 3 vertices and all regular complete bipartite graphs, the seven listed earlier (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22, and Higman-Sims) are the only known ones.

### Geodetic graphs

Every strongly regular graph with μ=1 is a geodetic graph, a graph in which every two vertices have a unique shortest path.[6] The only known strongly regular graphs with μ=1 are those where λ is 0, therefore triangle-free as well. These are called the Moore graphs and are explored below in more detail. Other combinations of parameters such as (400, 21, 2, 1) have not yet been ruled out. Despite ongoing research on the properties that a strongly regular graph with μ=1 would have,[7][8] it is not known whether any more exist or even whether their number is finite.[6] Only the elementary result is known, that λ cannot be 1 for such a graph.

## Algebraic properties of strongly regular graphs

### Basic relationship between parameters

The four parameters in an srg(v, k, λ, μ) are not independent: In order for an srg(v, k, λ, μ) to exist, the parameters must obey the following relation:

(v−k−1)μ=k(k−λ−1)

The above relation is derived through a counting argument as follows:

1. Imagine the vertices of the graph to lie in three levels. Pick any vertex as the root, in Level 0. Then its k neighbors lie in Level 1, and all other vertices lie in Level 2.
2. Vertices in Level 1 are directly connected to the root, hence they must have λ other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each vertex has degree k, there are k−λ−1 edges remaining for each Level 1 node to connect to vertices in Level 2. Therefore, there are k(k−λ−1) edges between Level 1 and Level 2.
3. Vertices in Level 2 are not directly connected to the root, hence they must have μ common neighbors with the root, and these common neighbors must all be in Level 1. There are (v−k−1) vertices in Level 2, and each is connected to μ vertices in Level 1. Therefore the number of edges between Level 1 and Level 2 is (v−k−1)μ.
4. Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.

This relation is a necessary condition for the existence of a strongly regular graph, but not a sufficient condition. For instance, the quadruple (21,10,4,5) obeys this relation, but there does not exist a strongly regular graph with these parameters.[9]

### Adjacency matrix equations

Let I denote the identity matrix and let J denote the matrix of ones, both matrices of order v. The adjacency matrix A of a strongly regular graph satisfies two equations.

First:

AJ=JA=kJ,

which is a restatement of the regularity requirement. This shows that k is an eigenvalue of the adjacency matrix with the all-ones eigenvector.

Second:

A2=kI+λA+μ(J−I−A)

which expresses strong regularity. The ij-th element of the left hand side gives the number of two-step paths from i to j. The first term of the right hand side gives the number of two-step paths from i back to i, namely k edges out and back in. The second term gives the number of two-step paths when i and j are directly connected. The third term gives the corresponding value when i and j are not connected. Since the three cases are mutually exclusive and collectively exhaustive, the simple additive equality follows.

Conversely, a graph whose adjacency matrix satisfies both of the above conditions and which is not a complete or null graph is a strongly regular graph.[10]

### Eigenvalues and graph spectrum

Since the adjacency matrix A is symmetric, it follows that its eigenvectors are orthogonal. We already observed one eigenvector above which is made of all ones, corresponding to the eigenvalue k. Therefore the other eigenvectors x must all satisfy Jx=0 where J is the all-ones matrix as before. Take the previously established equation:

A2=kI+λA+μ(J−I−A)

and multiply the above equation by eigenvector x:

A2x=kIx+λAx+μ(J−I−A)x

Call the corresponding eigenvalue p (not to be confused with λ the graph parameter) and substitute Ax=px, Jx=0 and Ix=x:

p2x=kx+λpx−μx−μpx

Eliminate x and rearrange to get a quadratic:

p2+(μ−λ)p−(k−μ)=0

This gives the two additional eigenvalues 12[(λ−μ)±(λ−μ)2+4(k−μ)]. There are thus exactly three eigenvalues for a strongly regular matrix.

Conversely, a connected regular graph with only three eigenvalues is strongly regular.[11]

Following the terminology in much of the strongly regular graph literature, the larger eigenvalue is called r with multiplicity f and the smaller one is called s with multiplicity g.

Since the sum of all the eigenvalues is the trace of the adjacency matrix, which is zero in this case, the respective multiplicities f and g can be calculated:

* Eigenvalue k has multiplicity 1.
* Eigenvalue r=12[(λ−μ)+(λ−μ)2+4(k−μ)] has multiplicity f=12[(v−1)−2k+(v−1)(λ−μ)(λ−μ)2+4(k−μ)]
* Eigenvalue s=12[(λ−μ)−(λ−μ)2+4(k−μ)] has multiplicity g=12[(v−1)+2k+(v−1)(λ−μ)(λ−μ)2+4(k−μ)]

As the multiplicities must be integers, their expressions provide further constraints on the values of v, k, μ, and λ.

Strongly regular graphs for which 2k+(v−1)(λ−μ)≠0 have integer eigenvalues with unequal multiplicities.

Strongly regular graphs for which 2k+(v−1)(λ−μ)=0 are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to

srg⁡(v,12(v−1),14(v−5),14(v−1)).

Their eigenvalues are r=−1+v2 and s=−1−v2, both of whose multiplicities are equal to v−12. Further, in this case, v must equal the sum of two squares, related to the Bruck–Ryser–Chowla theorem.

Further properties of the eigenvalues and their multiplicities are:[12]

* (A−rI)×(A−sI)=μ.J, therefore (k−r).(k−s)=μv
* λ−μ=r+s
* k−μ=−r×s
* k≥r
* Given an srg(v, k, λ, μ) with eigenvalues r and s, its complement srg(v, v − k − 1, v − 2 − 2k \+ μ, v − 2k \+ λ) has eigenvalues -1-s and -1-r.
* Alternate equations for the multiplicities are f=(s+1)k(k−s)μ(s−r) and g=(r+1)k(k−r)μ(r−s)
* The frame quotient condition: vk(v−k−1)=fg(r−s)2. As a corollary, v=(r−s)2 if and only if f,g=k,v−k−1 in some order.
* Krein conditions: (v−k−1)2(k2+r3)≥(r+1)3k2 and (v−k−1)2(k2+s3)≥(s+1)3k2
* Absolute bound: v≤f(f+3)2 and v≤g(g+3)2.
* Claw bound: if r+1>s(s+1)(μ+1)2, then μ=s2 or μ=s(s+1).

If any of the above conditions are violated for a set of parameters, then there exists no strongly regular graph for those parameters. Brouwer has compiled such lists of existence or non-existence here with reasons for non-existence if any. For example, there exists no srg(28,9,0,4) because that violates one of the Krein conditions and one of the absolute bound conditions.

### The Hoffman–Singleton theorem

As noted above, the multiplicities of the eigenvalues are given by

M±=12[(v−1)±2k+(v−1)(λ−μ)(λ−μ)2+4(k−μ)]

which must be integers.

In 1960, Alan Hoffman and Robert Singleton examined those expressions when applied on Moore graphs, which are strongly regular graphs that have λ = 0 and μ = 1. Such graphs are free of triangles (otherwise λ would exceed zero) and quadrilaterals (otherwise μ would exceed 1), hence they have a girth (smallest cycle length) of 5. Substituting the values of λ and μ in the equation (v−k−1)μ=k(k−λ−1), it can be seen that v=k2+1, and the eigenvalue multiplicities reduce to

M±=12[k2±2k−k24k−3]

For the multiplicities to be integers, the quantity 2k−k24k−3 must be rational, therefore either the numerator 2k−k2 is zero or the denominator 4k−3 is an integer.

If the numerator 2k−k2 is zero, the possibilities are:

* k = 0 and v = 1 yields a trivial graph with one vertex and no edges, and
* k = 2 and v = 5 yields the 5-vertex cycle graph C5, usually drawn as a regular pentagon.

If the denominator 4k−3 is an integer t, then 4k−3 is a perfect square t2, so k=t2+34. Substituting:

M±=12[(t2+34)2±t2+32−(t2+34)2t]32M±=(t2+3)2±8(t2+3)−(t2+3)2t=t4+6t2+9±−t4+2t2+15t=t4+6t2+9±(−t3+2t+15t)

Since both sides are integers, 15t must be an integer, therefore t is a factor of 15, namely t∈{±1,±3,±5,±15}, therefore k∈{1,3,7,57}. In turn:

* k = 1 and v = 2 yields a trivial graph of two vertices joined by an edge,
* k = 3 and v = 10 yields the Petersen graph,
* k = 7 and v = 50 yields the Hoffman–Singleton graph, discovered by Hoffman and Singleton in the course of this analysis, and
* k = 57 and v = 3250 famously predicts a graph that has neither been discovered since 1960, nor has its existence been disproven.[13]

The Hoffman-Singleton theorem states that there are no girth-5 Moore graphs except the ones listed above.

## See also

* Partial geometry
* Seidel adjacency matrix
* Two-graph

## Notes

1. ↑ Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101
2. ↑ Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag New York, 2001, p. 218.
3. ↑ https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)
4. ↑ Weisstein, Eric W.. "Schläfli graph". http://mathworld.wolfram.com/SchlaefliGraph.html.
5. ↑ Five $1,000 Problems (Update 2017), Online Encyclopedia of Integer Sequences, https://oeis.org/A248380/a248380.pdf, retrieved 2019-02-12
6. ↑ 6.0 6.1 Blokhuis, A. (1988), "Geodetic graphs of diameter two", Geometriae Dedicata 25 (1–3): 527–533, doi:10.1007/BF00191941
7. ↑ Deutsch, J.; Fisher, P. H. (2001), "On strongly regular graphs with μ=1", European Journal of Combinatorics 22 (3): 303–306, doi:10.1006/eujc.2000.0472
8. ↑ Belousov, I. N.; Makhnev, A. A. (2006), "On strongly regular graphs with μ=1 and their automorphisms", Doklady Akademii Nauk 410 (2): 151–155
9. ↑ Brouwer, A. E.; van Lint, J. H. (1984), "Strongly regular graphs and partial geometries", Enumeration and design (Waterloo, Ont., 1982), Academic Press, Toronto, ON, pp. 85–122, ISBN 0-12-379120-0, https://pure.tue.nl/ws/portalfiles/portal/2394798/595248.pdf
10. ↑ Cameron, P.J.; van Lint, J.H. (1991), Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, p. 37, ISBN 978-0-521-42385-4, https://archive.org/details/designsgraphscod0000came/page/37
11. ↑ Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag, New York, 2001, Lemma 10.2.1.
12. ↑ Brouwer & van Meldeghem, ibid.
13. ↑ Dalfó, C. (2019), "A survey on the missing Moore graph", Linear Algebra and Its Applications 569: 1–14, doi:10.1016/j.laa.2018.12.035

## References

* Andries Brouwer and Hendrik van Maldeghem (2022), Strongly Regular Graphs. Cambridge: Cambridge University Press. ISBN 1316512037. ISBN 978-1316512036
* A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
* Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1

## External links

* Eric W. Weisstein, Mathworld article with numerous examples.
* Gordon Royle, List of larger graphs and families.
* Andries E. Brouwer, Parameters of Strongly Regular Graphs.
* Brendan McKay, Some collections of graphs.
* Ted Spence, Strongly regular graphs on at most 64 vertices.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Strongly regular graph. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Strongly_regular_graph&oldid=4228026"