Strongly regular graph

Graph families defined by their automorphisms
distance-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	distance-regular	${\displaystyle {\boldsymbol {\leftarrow }}}$	strongly regular
${\displaystyle {\boldsymbol {\downarrow }}}$
symmetric (arc-transitive)	${\displaystyle {\boldsymbol {\leftarrow }}}$	t-transitive, t ≥ 2		skew-symmetric
${\displaystyle {\boldsymbol {\downarrow }}}$
(if connected) vertex- and edge-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	edge-transitive and regular	${\displaystyle {\boldsymbol {\rightarrow }}}$	edge-transitive
${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$
vertex-transitive	${\displaystyle {\boldsymbol {\rightarrow }}}$	regular	${\displaystyle {\boldsymbol {\rightarrow }}}$	(if bipartite) biregular
${\displaystyle {\boldsymbol {\uparrow }}}$
Cayley graph	${\displaystyle {\boldsymbol {\leftarrow }}}$	zero-symmetric		asymmetric

In graph theory, 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:

A graph of this kind is sometimes said to be an srg(v, k, λ, μ). Strongly regular graphs were introduced by Raj Chandra Bose in 1963.

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.

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

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

The four parameters in an srg(v, k, λ, μ) are not independent and must obey the following relation:

The above relation can be derived very easily through a counting argument as follows:

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 two equations. First,

which is a trivial restatement of the vertex degree requirement; incidentally, this shows that k is an eigenvalue of the adjacency matrix with an all-ones eigenvector. Second,

which expresses the strong regularity condition. The first term gives the number of 2-step paths from each vertex to all vertices, the second term the 1-step paths, and the third term the 0-step paths (so to speak). For the vertex pairs directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to λ. For the vertex pairs not directly connected by an edge, the equation reduces to the number of such 2-step paths being equal to μ. For the trivial self-pairs, the equation reduces to the degree being equal to k.

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

...
Wikipedia