In graph theory, a strongly regular graph (SRG) is a regular graph G = (V, E) with v vertices and degree k such that for some given integers λ , μ ≥ 0 {\displaystyle \lambda ,\mu \geq 0}
every two adjacent vertices have λ common neighbours, and every two non-adjacent vertices have μ common neighbours. Such a strongly regular graph is denoted by srg(v, k, λ, μ). Its complement graph is also strongly regular: it is an srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ). If a graph G is strongly regular with μ > 0, then G is distance-regular with diameter 2. Likewise, if G is strongly regular with λ = 1, then it is locally linear.
Etymology A strongly regular graph is denoted as an srg(v, k, λ, μ) in the literature. By convention, graphs which satisfy the definition trivially are excluded from detailed studies and lists of strongly regular graphs. These include the disjoint union of one or more equal-sized complete graphs, and their complements, the complete multipartite graphs with equal-sized independent sets. Andries Brouwer and Hendrik van Maldeghem (see #References) use an alternate but fully equivalent definition of a strongly regular graph based on spectral graph theory: a strongly regular graph is a finite regular graph that has exactly three eigenvalues, only one of which is equal to the degree k, of multiplicity 1. This automatically rules out fully connected graphs (which have only two distinct eigenvalues, not three) and disconnected graphs (for which the multiplicity of the degree k is equal to the number of different connected components, which would therefore exceed one). Much of the literature, including Brouwer, refers to the larger eigenvalue as r (with multiplicity f) and the smaller one as s (with multiplicity g).
History Strongly regular graphs were introduced by R.C. Bose in 1963. They built upon earlier work in the 1950s in the then-new field of spectral graph theory.
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 n × n square rook's graph, i.e., the line graph of a balanced complete bipartite graph Kn,n, is an srg(n2, 2n − 2, n − 2, 2). The parameters for n = 4 coincide with those of the Shrikhande graph, but the two graphs are not isomorphic. (The vertex neighborhood for the Shrikhande graph is a hexagon, while that for the rook graph is two triangles.) The line graph of a complete graph Kn is an srg ( ( n 2 ) , 2 ( n − 2 ) , n − 2 , 4 ) {\textstyle \operatorname {srg} \left({\binom {n}{2}},2(n-2),n-2,4\right)} . The three Chang graphs are srg(28, 12, 6, 4), the same as the line graph of K8, but these four graphs are not isomorphic. Every generalized quadrangle of order (s, t) gives an srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1) as its line graph. For example, GQ(2, 4) gives srg(27, 10, 1, 5) as its line graph. The Schläfli graph is an srg(27, 16, 10, 8) and is the complement of the aforementioned line graph on GQ(2, 4). The Hoffman–Singleton graph is an srg(50, 7, 0, 1). The Gewirtz graph is an srg(56, 10, 0, 2). The M22 graph aka the Mesner 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 Cameron graph is an srg(231, 30, 9, 3). The Berlekamp–van Lint–Seidel graph is an srg(243, 22, 1, 2). The McLaughlin graph is an srg(275, 112, 30, 56). The Paley graph of order q is an srg(q, (q − 1)/2, (q − 5)/4, (q − 1)/4). The smallest Paley graph, with q = 5, is the 5-cycle (above). Self-complementary arc-transitive graphs are strongly regular. 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 v + λ = 2k. 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 offered a $1000 prize for the solution to this problem.
Triangle-free graphs The strongly regular graphs with λ = 0 are triangle free. Apart from the complete graphs on at most two vertices and all regular complete bipartite graphs, the seven listed earlier (pentagon, Petersen, Clebsch, Hoffman-Singleton, Gewirtz, Mesner-M22, and Higman-Sims) are the only known ones.
Geodetic graphs Every strongly regular graph with μ = 1 {\displaystyle \mu =1} is a geodetic graph, a graph in which every two vertices have a unique shortest path. The only known strongly regular graphs with μ = 1 {\displaystyle \mu =1} are those where λ {\displaystyle \lambda } is 0, therefore triangle-free as well. These are called the Moore graphs and are explored below in more detail. 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 μ = 1 {\displaystyle \mu =1} would have, it is not known whether any more exist or even whether their number is finite. Only the elementary result is known, that λ {\displaystyle \lambda } cannot be 1 for such a graph.
Algebraic properties of strongly regular graphs
Basic relationship between parameters The four parameters in an srg(v, k, λ, μ) are not independent: In order for an srg(v, k, λ, μ) to exist, the parameters must obey the following relation:
… excerpt ends here. Continue reading the full article.
