Strongly regular graph

From Wikipedia, the free encyclopedia

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 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.

Contents 1 Properties 2 Examples 3 See also 4 External links 5 References

[edit] 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+λ).

[edit] Examples

• The cycle of length 5.
• Petersen graph
• Hoffman-Singleton graph
• Higman-Sims graph
• Paley graphs
• Square rook's graphs
• The Schläfli graph

[edit] See also

• Seidel adjacency matrix

[edit] External links

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

[edit] 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