Strongly regular graph

From Wikipedia, the free encyclopedia

You have new messages (last change).

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 essentially a distance-regular graph with diameter 2.

[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
    • A2 + (μ−λ) 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
\frac{1}{2} [(\lambda-\mu) \pm \sqrt\nu] ,

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

\frac{1}{2} \left[ (v-1) \mp \frac{N}{\sqrt\nu} \right] ,

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

[edit] References

  • Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1
This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../s/t/r/Strongly_regular_graph.html"