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	$\rightarrow$	distance-regular	$\leftarrow$	strongly regular
$\downarrow$
symmetric (arc-transitive)	$\leftarrow$	t-transitive, t ≥ 2
$\downarrow$(if connected)
vertex- and edge-transitive	$\rightarrow$	edge-transitive and regular	$\rightarrow$	edge-transitive
$\downarrow$		$\downarrow$
vertex-transitive	$\rightarrow$	regular
$\uparrow$
Cayley graph		skew-symmetric		asymmetric

In graph theory, a discipline within mathematics, a strongly regular graph is defined as follows. 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.

Properties

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

$(v-k-1)\mu = k(k-\lambda-1)$^{[citation needed]}

• Let I denote the identity matrix (of order v) and let J denote the matrix whose entries all equal 1. The adjacency matrix A of a strongly regular graph satisfies these properties :
  • $AJ = kJ$
    (This is a trivial restatement of the vertex degree requirement).
  • ${A}^{2} + (\mu-\lambda){A} + (\mu-k){I} = \mu {J}$
    (The first term gives the number of 2-step paths from each vertex to all vertices. For the vertex pairs directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to $\lambda$. For the vertex pairs not directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to $\mu$. For the trivial self-pairs, the equation reduces to the degree being equal to k).

• The graph has exactly three eigenvalues:
  • $k$ whose multiplicity is 1
  • $\frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]$ whose multiplicity is $\frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]$
  • $\frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]$ whose multiplicity is $\frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]$

• Strongly regular graphs for which $2k+(v-1)(\lambda-\mu) = 0$ are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to $srg\left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right)$.

• Strongly regular graphs for which $2k+(v-1)(\lambda-\mu) \ne 0$ have integer eigenvalues with unequal multiplicities.

• 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 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 Schläfli graph is an srg(27,16,10,8).
• The Chang graphs are srg(28,12,6,4).
• The Hoffman–Singleton graph is an srg(50,7,0,1).
• The Sims-Gewirtz graph is an (56,10,0,2).
• The M22 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 Paley graph of order q is an srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4).
• The n × n square rook's graph is an srg(n², 2n − 2, n − 2, 2).

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

The strongly regular graphs with λ=0 are triangle free. The seven listed above are the only known ones. Strongly regular graphs with λ=0 and μ=1 are called Moore graphs. Again the three graphs given above, with parameters (5,2,0,1), (10,3,0,1) and (50,7,0,1), are the only known ones. The only other possible set of parameters yielding a Moore graph is (57^2+1,57,0,1); it is unknown if such a graph exists, and if so, whether or not it is unique.

See also

• Seidel adjacency matrix

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

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