Strongly regular graph

The Paley graph of order 13, a strongly regular graph with parameters srg(13,6,2,3).

Graph families defined by their automorphisms
distance-transitive		distance-regular		strongly regular
symmetric (arc-transitive)		t-transitive, t ≥ 2
(if connected)
vertex- and edge-transitive		edge-transitive and regular		edge-transitive
vertex-transitive		regular
Cayley graph				skew-symmetric

Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:

• Every two adjacent vertices have λ common neighbours.

• Every two non-adjacent vertices have μ common neighbours.

A graph of this kind is sometimes said to be an srg(v,k,λ,μ).

Some authors exclude^{[citation needed]} graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized complete graphs, and their complements, the Turán graphs.

A strongly regular graph is a distance-regular graph with diameter 2, but only if μ is non-zero.

Properties

• The four parameters in an srg(v,k,λ,μ) are not independent, as it is easy to show that (v−k−1)μ = k(k−λ−1).

• Let I denote the identity matrix and let J denote the matrix whose entries all equal 1. The adjacency matrix A of a strongly regular graph satisfies these properties :
  • A J = k J
  • A² + (μ−λ) A + (μ−k) I = μ J.

• The graph has exactly three eigenvalues, one of which is the degree k. The other eigenvalues can be expressed in terms of the parameters; they are

where ν = (λ − μ)² + 4(k − μ). The multiplicities of the eigenvalues are

where N = 2k + (v − 1)(λ − μ).

• There are two kinds of strongly regular graph. If N = 0, then we have an srg(v, (v−1)/2, (v−5)/4, (v−1)/4). This kind is called a conference graph because of its connection with symmetric conference matrices. If N is nonzero, then the eigenvalues are all integers and their multiplicities are not equal.

• The complement of an srg(v,k,λ,μ) is also strongly regular. It is an srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

Examples

• The Shrikhande graph is an example which is not a distance-transitive graph
• The cycle of length 5
• Petersen graph
• Hoffman-Singleton graph
• Higman-Sims graph
• Paley graphs
• Square rook's graphs
• The Schläfli graph ^[1]

See also

• Seidel adjacency matrix

Notes

References

• 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

• Mathworld article with numerous examples.
• List of larger graphs and families.