Strongly regular graph

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 complete multipartite graphs with equal-sized independent sets.
The complement of an srg("v", "k", λ, μ) is also strongly regular. It is an srg("v", "v−k"−1, "v"−2−2"k"+μ, "v"−2"k"+λ).
A strongly regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero.
It is a locally linear graph whenever λ=1.
Properties.
Relationship between Parameters.
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:
Adjacency Matrix.
Let "I" denote the identity matrix and let "J" denote the matrix of ones, both matrices of order "v". The adjacency matrix "A" of a strongly regular graph satisfies two equations. First:
which is a trivial restatement of the regularity requirement. This shows that "k" is an eigenvalue of the adjacency matrix with the all-ones eigenvector. Second is a quadratic equation,
which expresses strong regularity. The "ij"-th element of the left hand side gives the number of two-step paths from "i" to "j". The first term of the RHS gives the number of self-paths from "i" to "i", namely "k" edges out and back in. The second term gives the number of two-step paths when "i" and "j" are directly connected. The third term gives the corresponding value when "i" and "j" are not connected. Since the three cases are mutually exclusive and collectively exhaustive, the simple additive equality follows.
Conversely, a graph whose adjacency matrix satisfies both of the above conditions and which is not a complete or null graph is a strongly regular graph.
Eigenvalues.
The adjacency matrix of the graph has exactly three eigenvalues:
As the multiplicities must be integers, their expressions provide further constraints on the values of "v", "k", "μ", and "λ", related to the so-called "Krein conditions".
Strongly regular graphs for which formula_12 are called conference graphs because of their connection with symmetric conference matrices. Their parameters reduce to
Strongly regular graphs for which formula_14 have integer eigenvalues with unequal multiplicities.
Conversely, a connected regular graph with only three eigenvalues is strongly regular.
Examples.
A strongly regular graph is called primitive if both the graph and its complement are connected. All the above graphs are primitive, as otherwise μ=0 or λ=k.
Conway's 99-graph problem asks for the construction of an srg(99, 14, 1, 2). It is unknown whether a graph with these parameters exists, and John Horton Conway has offered a $1000 prize for the solution to this problem.
Triangle-free graphs, Moore graphs, and geodetic graphs.
The strongly regular graphs with λ = 0 are triangle free. Apart from the complete graphs on less than 3 vertices and all complete bipartite graphs the seven listed above (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22, and Higman-Sims) are the only known ones. Strongly regular graphs with λ = 0 and μ = 1 are Moore graphs with girth 5. Again the three graphs given above (pentagon, Petersen, and Hoffman-Singleton), 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 (3250, 57, 0, 1); it is unknown if such a graph exists, and if so, whether or not it is unique.
More generally, every strongly regular graph with formula_16 is a geodetic graph, a graph in which every two vertices have a unique unweighted shortest path. The only known strongly regular graphs with formula_16 are the Moore graphs. It is not possible for such a graph to have formula_18, but other combinations of parameters such as (400, 21, 2, 1) have not yet been ruled out. Despite ongoing research on the properties that a strongly regular graph with formula_16 would have, it is not known whether any more exist or even whether their number is finite.