strongly regular graph
   HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a strongly regular graph (SRG) is defined as follows. Let be a
regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegr ...
with vertices and degree . is said to be strongly regular if there are also
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s and such that: * Every two adjacent vertices have common neighbours. * Every two non-adjacent vertices have common neighbours. The
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
of an is also strongly regular. It is a . A strongly regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero. It is a
locally linear graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can b ...
whenever .


Etymology

A strongly regular graph is denoted 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 graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
s, and their complements, the complete
multipartite graph In graph theory, a part of mathematics, a -partite graph is a graph whose vertices are (or can be) partitioned into different independent sets. Equivalently, it is a graph that can be colored with colors, so that no two endpoints of an edge ...
s with equal-sized independent sets.
Andries Brouwer Andries Evert Brouwer (born 1951) is a Dutch mathematician and computer programmer, Professor Emeritus at Eindhoven University of Technology (TU/e). He is known as the creator of the greatly expanded 1984 to 1985 versions of the roguelike compu ...
and Hendrik van Maldeghem (see #References) use an alternate but fully equivalent definition of a strongly regular graph based on
spectral graph theory In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matri ...
: 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 (whose 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, refer to the larger eigenvalue as ''r'' (with multiplicty ''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 In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matri ...
.


Examples

* The cycle of length 5 is an srg(5, 2, 0, 1). * The
Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...
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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V a ...
''K''''n'',''n'', is an srg(''n''2, 2''n'' − 2, ''n'' − 2, 2). The parameters for coincide with those of the Shrikhande graph, but the two graphs are not isomorphic. * The
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
of a complete graph ''Kn'' is an \operatorname\left(\binom, 2(n - 2), n - 2, 4\right). * The
Chang graphs In the mathematical field of graph theory, the Chang graphs are a set of three 12- regular undirected graphs, each with 28 vertices and 168 edges. They are strongly regular, with the same parameters and spectra as the line graph ''L''(''K''8) ...
are srg(28, 12, 6, 4), the same as the line graph of ''K''8, but these four graphs are not isomorphic. * The
line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
of a
generalized quadrangle In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles (yet containing many quadrangles). A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = ...
GQ(2, 4) is an srg(27, 10, 1, 5). In fact every generalized quadrangle of order (s, t) gives a strongly regular graph in this way: to wit, an srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1). * The
Schläfli graph In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16- regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8 ...
is an srg(27, 16, 10, 8). * The
Hoffman–Singleton graph In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7- regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman ...
is an srg(50, 7, 0, 1). * The
Sims-Gewirtz graph The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation.M22 graph The M22 graph, also called the Mesner graph or Witt graph is the unique strongly regular graph with parameters (77, 16, 0, 4). Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. A ...
aka the
Mesner graph The M22 graph, also called the Mesner graph or Witt graph is the unique strongly regular graph with parameters (77, 16, 0, 4). Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. A ...
is an srg(77, 16, 0, 4). * The
Brouwer–Haemers graph In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20- regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its const ...
is an srg(81, 20, 1, 6). * The
Higman–Sims graph In mathematical graph theory, the Higman–Sims graph is a 22- regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and ...
is an srg(100, 22, 0, 6). * The
Local McLaughlin graph In the mathematical field of graph theory, the McLaughlin graph is a strongly regular graph with parameters (275,112,30,56), and is the only such graph. The group theorist Jack McLaughlin discovered that the automorphism group of this graph had a ...
is an srg(162, 56, 10, 24). * The Cameron graph is an srg(231, 30, 9, 3). * The
Berlekamp–van Lint–Seidel graph In graph theory, the Berlekamp–Van Lint–Seidel graph is a locally linear strongly regular graph with parameters (243,22,1,2). This means that it has 243 vertices, 22 edges per vertex (for a total of 2673 edges), exactly one shared neighbor pe ...
is an srg(243, 22, 1, 2). * The McLaughlin graph is an srg(275, 112, 30, 56). * The
Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, ...
of order ''q'' is an srg(''q'', (''q'' − 1)/2, (''q'' − 5)/4, (''q'' − 1)/4). The smallest Paley graph, with , 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 or .
Conway's 99-graph problem In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices ...
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 John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
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 less than 3 vertices and all 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 \mu = 1 is a geodetic graph, a graph in which every two vertices have a unique unweighted shortest path. The only known strongly regular graphs with \mu = 1 are those where \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 \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 \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. They must obey the following relation: :(v - k - 1)\mu = k(k - \lambda - 1) The above relation is derived through a counting argument as follows: # Imagine the vertices of the graph to lie in three levels. Pick any vertex as the root, in Level 0. Then its ''k'' neighbors lie in Level 1, and all other vertices lie in Level 2. # Vertices in Level 1 are directly connected to the root, hence they must have λ other neighbors in common with the root, and these common neighbors must also be in Level 1. Since each vertex has degree ''k'', there are k - \lambda - 1 edges remaining for each Level 1 node to connect to nodes in Level 2. Therefore, there are k (k - \lambda - 1) edges between Level 1 and Level 2. # Vertices in Level 2 are not directly connected to the root, hence they must have μ common neighbors with the root, and these common neighbors must all be in Level 1. There are (v - k - 1) vertices in Level 2, and each is connected to μ nodes in Level 1. Therefore the number of edges between Level 1 and Level 2 is (v - k - 1)\mu. # Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.


Adjacency matrix equations

Let ''I'' denote the
identity matrix In linear algebra, the identity matrix of size n is the n\times n square matrix with ones on the main diagonal and zeros elsewhere. Terminology and notation The identity matrix is often denoted by I_n, or simply by I if the size is immaterial or ...
and let ''J'' denote the matrix of ones, both matrices of order ''v''. The
adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...
''A'' of a strongly regular graph satisfies two equations. First: :AJ = JA = kJ, which is a restatement of the regularity requirement. This shows that ''k'' is an eigenvalue of the adjacency matrix with the all-ones eigenvector. Second: :A^2 = kI + \lambda + \mu(J - I - A) 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 right hand side gives the number of two-step paths from ''i'' back 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 In logic and probability theory, two events (or propositions) are mutually exclusive or disjoint if they cannot both occur at the same time. A clear example is the set of outcomes of a single coin toss, which can result in either heads or tails ...
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 and graph spectrum

Since the adjacency matrix A is symmetric, it follows that its eigenvectors are orthogonal. We already observed one eigenvector above which is made of all ones, corresponding to the eigenvalue ''k''. Therefore the other eigenvectors ''x'' must all satisfy Jx = 0 where ''J'' is the all-ones matrix as before. Take the previously established equation: :A^2 = kI + \lambda + \mu(J - I - A) and multiply the above equation by eigenvector ''x'': :A^2 x = kIx + \lambdax + \mu(J - I - A)x Call the corresponding eigenvalue ''p'' (not to be confused with \lambda the graph parameter) and substitute Ax = px, Jx = 0 and Ix = x: :p^2 x = kx + \lambda p x - \mu x - \mu p x Eliminate x and rearrange to get a quadratic: :p^2 + (\mu - \lambda ) p - (k - \mu) = 0 This gives the two additional eigenvalues \frac\left \lambda - \mu) \pm \sqrt\,\right/math>. There are thus exactly three eigenvalues for a strongly regular matrix. Conversely, a connected regular graph with only three eigenvalues is strongly regular. Following the terminology in much of the strongly regular graph literature, the larger eigenvalue is called ''r'' with multiplicity ''f'' and the smaller one is called ''s'' with multiplicity ''g''. Since the sum of all the eigenvalues is the trace of the adjacency matrix, which is zero in this case, the respective multiplicities ''f'' and ''g'' can be calculated: * Eigenvalue ''k'' has multiplicity 1. * Eigenvalue r = \frac\left \lambda - \mu) + \sqrt\,\right/math> has multiplicity f = \frac\left v - 1) - \frac\right/math>. * Eigenvalue s = \frac\left \lambda - \mu) - \sqrt\,\right/math> has multiplicity g = \frac\left v - 1) + \frac\right/math>. As the multiplicities must be integers, their expressions provide further constraints on the values of ''v'', ''k'', ''μ'', and ''λ''. Strongly regular graphs for which 2k + (v - 1)(\lambda - \mu) \ne 0 have integer eigenvalues with unequal multiplicities. 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 : \operatorname\left(v, \frac(v - 1), \frac(v - 5), \frac(v - 1)\right). Their eigenvalues are r =\frac and s = \frac, both of whose multiplicities are equal to \frac. Further, in this case, ''v'' must equal the sum of two squares, related to the Bruck–Ryser–Chowla theorem. Further properties of the eigenvalues and their multiplicities are: * (A - rI)\times(A - sI) = \mu.J, therefore (k - r).(k - s) = \mu v * \lambda - \mu = r + s * k - \mu = -r\times s * k \ge r * Given an with eigenvalues ''r'' and ''s'', its complement has eigenvalues ''-1-s'' and ''-1-r''. * Alternate equations for the multiplicities are f =\frac and g =\frac * The frame quotient condition: v k (v-k-1) = f g (r-s)^2. As a corollary, v = (r-s)^2
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
= in some order. * Krein conditions: (v-k-1)^2 (k^2 + r^3) \ge (r+1)^3 k^2 and (v-k-1)^2 (k^2 + s^3) \ge (s+1)^3 k^2 * Absolute bound: v \le \frac and v \le \frac. * Claw bound: if r + 1 > \frac, then \mu = s^2 or \mu = s(s+1). If the above condition(s) are violated for any set of parameters, then there exists no strongly regular graph for those parameters. Brouwer has compiled such lists of existence or non-existenc
here
with reasons for non-existence if any.


The Hoffman–Singleton theorem

As noted above, the multiplicities of the eigenvalues are given by :M_ = \frac\left v - 1) \pm \frac\right/math> which must be integers. In 1960, Alan Hoffman and Robert Singleton examined those expressions when applied on
Moore graph In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must ...
s that have ''λ'' = 0 and ''μ'' = 1. Such graphs are free of triangles (otherwise ''λ'' would exceed zero) and quadrilaterals (otherwise ''μ'' would exceed 1), hence they have a girth (smallest cycle length) of 5. Substituting the values of ''λ'' and ''μ'' in the equation (v - k - 1)\mu = k(k - \lambda - 1), it can be seen that v = k^2 + 1, and the eigenvalue multiplicities reduce to :M_ = \frac\left ^2 \pm \frac\right/math> For the multiplicities to be integers, the quantity \frac must be rational, therefore either the numerator 2k - k^2 is zero or the denominator \sqrt is an integer. If the numerator 2k - k^2 is zero, the possibilities are: * ''k'' = 0 and ''v'' = 1 yields a trivial graph with one vertex and no edges, and * ''k'' = 2 and ''v'' = 5 yields the 5-vertex
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
C_5, usually drawn as a regular pentagon. If the denominator \sqrt is an integer ''t'', then 4k - 3 is a perfect square t^2, so k = \frac. Substituting: :\begin M_ &= \frac \left left(\frac\right)^2 \pm \frac\right\\ 32 M_ &= (t^2 + 3)^2 \pm \frac \\ &= t^4 + 6t^2 + 9 \pm \frac \\ &= t^4 + 6t^2 + 9 \pm \left(-t^3 + 2t + \frac\right) \end Since both sides are integers, \frac must be an integer, therefore ''t'' is a factor of 15, namely t \in \, therefore k \in \. In turn: * ''k'' = 1 and ''v'' = 2 yields a trivial graph of two vertices joined by an edge, * ''k'' = 3 and ''v'' = 10 yields the
Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...
, * ''k'' = 7 and ''v'' = 50 yields the
Hoffman–Singleton graph In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7- regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman ...
, discovered by Hoffman and Singleton in the course of this analysis, and * ''k'' = 57 and ''v'' = 3250 predicts a famous graph that has neither been discovered since 1960, nor has its existence been disproven. The Hoffman-Singleton theorem states that there are no strongly regular girth-5 Moore graphs except the ones listed above.


See also

*
Partial geometry An incidence structure C=(P,L,I) consists of points P, lines L, and flags I \subseteq P \times L where a point p is said to be incident with a line l if (p,l) \in I. It is a (finite) partial geometry if there are integers s,t,\alpha\geq 1 such that ...
* Seidel adjacency matrix *
Two-graph In mathematics, a two-graph is a set of (unordered) triples chosen from a finite vertex set ''X'', such that every (unordered) quadruple from ''X'' contains an even number of triples of the two-graph. A regular two-graph has the property that every ...


Notes


References

*
Andries Brouwer Andries Evert Brouwer (born 1951) is a Dutch mathematician and computer programmer, Professor Emeritus at Eindhoven University of Technology (TU/e). He is known as the creator of the greatly expanded 1984 to 1985 versions of the roguelike compu ...
and Hendrik van Maldeghem (2022), ''Strongly Regular Graphs''. Cambridge: Cambridge University Press. . * A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), ''Distance Regular Graphs''. Berlin, New York: Springer-Verlag. , *
Chris Godsil Christopher David Godsil is a professor and the former Chair at the Department of Combinatorics and Optimization in the faculty of mathematics at the University of Waterloo. He wrote the popular textbook on algebraic graph theory, entitled ' ...
and Gordon Royle (2004), ''Algebraic Graph Theory''. New York: Springer-Verlag.


External links

*
Eric W. Weisstein Eric Wolfgang Weisstein (born March 18, 1969) is an American mathematician and encyclopedist who created and maintains the encyclopedias ''MathWorld'' and ''ScienceWorld''. In addition, he is the author of the '' CRC Concise Encyclopedia of M ...

Mathworld article with numerous examples.
*
Gordon Royle Gordon F. Royle is a professor at the School of Mathematics and Statistics at The University of Western Australia. Royle is the co-author (with Chris Godsil) of the book ''Algebraic Graph Theory'' (Springer Verlag, 2001, ). Royle is also known ...

List of larger graphs and families.
* Andries E. Brouwer
Parameters of Strongly Regular Graphs.
* Brendan McKay
Some collections of graphs.
*
Ted Spence TED may refer to: Economics and finance * TED spread between U.S. Treasuries and Eurodollar Education * ''Türk Eğitim Derneği'', the Turkish Education Association ** TED Ankara College Foundation Schools, Turkey ** Transvaal Education Depar ...

Strongly regular graphs on at most 64 vertices.
{{DEFAULTSORT:Strongly Regular Graph Graph families Algebraic graph theory Regular graphs