Content deleted Content added
Citation bot (talk | contribs) Alter: issue, journal. Add: s2cid. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 331/373 |
m →Geodetic graphs: Rm superfluous word. |
||
| (34 intermediate revisions by 9 users not shown) | |||
Line 1:
{{Short description|Concept in graph theory}}
[[Image:Paley13.svg|thumb|upright=1.1|The [[Paley graph]] of order 13, a strongly regular graph with parameters
{{Graph families defined by their automorphisms}}
In [[graph theory]], a '''strongly regular graph'''
▲* Every two [[adjacent vertices]] have λ common neighbours.
▲* Every two non-adjacent vertices have μ common neighbours.
A strongly regular graph is a [[distance-regular graph]] with diameter 2 whenever μ is non-zero. It is a [[locally linear graph]] whenever {{
A graph of this kind is sometimes said to be an srg(''v'', ''k'', λ, μ). Strongly regular graphs were introduced by [[Raj Chandra Bose|R.C. Bose]] in 1963.<ref>https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)</ref>▼
==Etymology==
[[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'').
▲The [[complement graph|complement]] of an {{nowrap|srg(''v'', ''k'', λ, μ)}} is also strongly regular. It is an {{nowrap|srg(''v'', ''v'' − ''k'' − 1, ''v'' − 2 − 2''k'' + μ, ''v'' − 2''k'' + λ)}}.
==History==
▲A strongly regular graph is a [[distance-regular graph]] with diameter 2 whenever μ is non-zero. It is a [[locally linear graph]] whenever {{nowrap|λ {{=}} 1}}.
▲
==Examples==
Line 20 ⟶ 24:
* 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]] ''K''<sub>''n'',''n''</sub>, is an srg(''n''<sup>2</sup>, 2''n'' − 2, ''n'' − 2, 2). The parameters for {{nowrap|''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 ''K<sub>n</sub>'' is an <math display="inline">\operatorname{srg}\left(\binom{n}{2}, 2(n - 2), n - 2, 4\right)</math>.
* The three [[Chang graphs]] are srg(28, 12, 6, 4), the same as the line graph of ''K''<sub>8</sub>, but these four graphs are not isomorphic.
*
* The [[Schläfli graph]] is an srg(27, 16, 10, 8) and is the complement of the aforementioned line graph on GQ(2, 4).<ref>{{MathWorld | urlname=SchlaefliGraph | title=Schläfli graph|mode=cs2}}</ref>
* The [[Hoffman–Singleton graph]] is an srg(50, 7, 0, 1).
* The [[
* 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).
Line 35 ⟶ 39:
* 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 {{nowrap|''q'' {{=}} 5}}, is the 5-cycle (above).
* [[Self-complementary graph|
A strongly regular graph is called '''primitive''' if both the graph and its complement are connected. All the above graphs are primitive, as otherwise {{nowrap|μ {{=}} 0}} or {{nowrap|''v'' + λ {{=}} 2''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]] offered a $1000 prize for the solution to this problem.<ref>{{citation
Line 48 ⟶ 52:
===Triangle-free graphs===
The strongly regular graphs with λ = 0 are [[triangle-free graph|triangle free]]. Apart from the complete graphs on
===Geodetic graphs===
Every strongly regular graph with <math>\mu = 1</math> is a [[geodetic graph]], a graph in which every two vertices have a unique [[Shortest path problem|
| last1 = Blokhuis | first1 = A.
| last2 = Brouwer | first2 = A. E. | authorlink = Andries Brouwer
Line 63 ⟶ 67:
| year = 1988
| s2cid = 189890651
}}</ref> The only known strongly regular graphs with <math>\mu = 1</math> are those where <math>\lambda</math> is 0, therefore triangle-free as well. These are called the Moore graphs and are [[#The Hoffman–Singleton theorem|explored below in more detail]].
| last1 = Deutsch | first1 = J.
| last2 = Fisher | first2 = P. H.
Line 84 ⟶ 88:
| volume = 410
| year = 2006
}}</ref> it is not known whether any more exist or even whether their number is finite.<ref name=bb/> Only the elementary result is known, that <math>\lambda</math> 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
:<math>(v - k - 1)\mu = k(k - \lambda - 1)</math>
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 <math>k - \lambda - 1</math> edges remaining for each Level 1 node to connect to
# 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 <math>(v - k - 1)</math> vertices in Level 2, and each is connected to μ
# Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.
This relation is a [[necessary condition]] for the existence of a strongly regular graph, but not a [[sufficient condition]]. For instance, the quadruple (21,10,4,5) obeys this relation, but there does not exist a strongly regular graph with these parameters.<ref>{{citation
| last1 = Brouwer | first1 = A. E.
| last2 = van Lint | first2 = J. H.
| contribution = Strongly regular graphs and partial geometries
| contribution-url = https://pure.tue.nl/ws/portalfiles/portal/2394798/595248.pdf
| isbn = 0-12-379120-0
| mr = 782310
| pages = 85–122
| publisher = Academic Press, Toronto, ON
| title = Enumeration and design (Waterloo, Ont., 1982)
| year = 1984}}</ref>
===Adjacency matrix equations===
Line 116 ⟶ 132:
and multiply the above equation by eigenvector ''x'':
:<math>A^2 x = kIx + \lambda{A}x + \mu(J - I - A)x</math>
Call the corresponding eigenvalue ''
:<math>
Eliminate x and rearrange to get a quadratic:
:<math>
This gives the two additional eigenvalues <math>\frac{1}{2}\left[(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]</math>. There are thus exactly three eigenvalues for a strongly regular matrix.
Line 125 ⟶ 141:
Conversely, a connected regular graph with only three eigenvalues is strongly regular.<ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag, New York, 2001, Lemma 10.2.1.</ref>
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 (linear algebra)|trace of the adjacency matrix]], which is zero in this case, the respective multiplicities can be calculated:▼
▲Since the sum of all the eigenvalues is the [[Trace (linear algebra)|trace of the adjacency matrix]], which is zero in this case, the respective multiplicities ''f'' and ''g'' can be calculated:
* Eigenvalue ''k'' has [[Multiplicity (mathematics)|multiplicity]] 1.
* Eigenvalue <math>r = \frac{1}{2}\left[(\lambda - \mu) + \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]</math> has multiplicity <math>f = \frac{1}{2}\left[(v - 1) - \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>
* Eigenvalue <math>s = \frac{1}{2}\left[(\lambda - \mu) - \sqrt{(\lambda - \mu)^2 + 4(k-\mu)}\,\right]</math> has multiplicity <math>g = \frac{1}{2}\left[(v - 1) + \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>
As the multiplicities must be integers, their expressions provide further constraints on the values of ''v'', ''k'', ''μ'', and ''λ''.
Line 136 ⟶ 154:
Strongly regular graphs for which <math>2k + (v - 1)(\lambda - \mu) = 0</math> are called [[conference graph]]s because of their connection with symmetric [[conference matrix|conference matrices]]. Their parameters reduce to
: <math>\operatorname{srg}\left(v, \frac{1}{2}(v - 1), \frac{1}{4}(v - 5), \frac{1}{4}(v - 1)\right).</math>
Their eigenvalues are <math>r =\frac{-1 + \sqrt{v}}{2}</math> and <math>s = \frac{-1 - \sqrt{v}}{2}</math>, both of whose multiplicities are equal to <math>\frac{v-1}{2}</math>. 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:<ref>Brouwer & van Meldeghem, ibid.</ref>
* <math>(A - rI)\times(A - sI) = \mu.J</math>, therefore <math>(k - r).(k - s) = \mu v</math>
* <math>\lambda - \mu = r + s</math>
* <math>k - \mu = -r\times s</math>
* <math>k \ge r</math>
* Given an {{nowrap|srg(''v'', ''k'', λ, μ)}} with eigenvalues ''r'' and ''s'', its complement {{nowrap|srg(''v'', ''v'' − ''k'' − 1, ''v'' − 2 − 2''k'' + μ, ''v'' − 2''k'' + λ)}} has eigenvalues ''-1-s'' and ''-1-r''.
* Alternate equations for the multiplicities are <math>f =\frac{(s+1)k(k-s)}{\mu(s-r)}</math> and <math>g =\frac{(r+1)k(k-r)}{\mu(r-s)}</math>
* The frame quotient condition: <math>v k (v-k-1) = f g (r-s)^2</math>. As a corollary, <math>v = (r-s)^2</math> [[if and only if]] <math>{f,g} = {k, v-k-1}</math> in some order.
* Krein conditions: <math>(v-k-1)^2 (k^2 + r^3) \ge (r+1)^3 k^2</math> and <math>(v-k-1)^2 (k^2 + s^3) \ge (s+1)^3 k^2</math>
* Absolute bound: <math>v \le \frac{f(f+3)}{2}</math> and <math>v \le \frac{g(g+3)}{2}</math>.
* Claw bound: if <math>r + 1 > \frac{s(s+1)(\mu+1)}{2}</math>, then <math>\mu = s^2</math> or <math>\mu = s(s+1)</math>.
If any of the above conditions are violated for a set of parameters, then there exists no strongly regular graph for those parameters. Brouwer has compiled such lists of existence or non-existence [https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html here] with reasons for non-existence if any. For example, there exists no srg(28,9,0,4) because that violates one of the Krein conditions and one of the absolute bound conditions.
===The Hoffman–Singleton theorem===
Line 142 ⟶ 174:
which must be integers.
In 1960, [[Alan J. Hoffman|Alan Hoffman]] and Robert Singleton examined those expressions when applied on [[Moore graph]]s, which are strongly regular graphs 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 <math>(v - k - 1)\mu = k(k - \lambda - 1)</math>, it can be seen that <math>v = k^2 + 1</math>, and the eigenvalue multiplicities reduce to
:<math>M_{\pm} = \frac{1}{2}\left[k^2 \pm \frac{2k - k^2}{\sqrt{4k - 3}}\right]</math>
Line 153 ⟶ 185:
If the denominator <math>\sqrt{4k - 3}</math> is an integer ''t'', then <math>4k - 3</math> is a perfect square <math>t^2</math>, so <math>k = \frac{t^2 + 3}{4}</math>. Substituting:
:<math>\begin{align}
&= t^4 + 6t^2 + 9 \pm \left(-t^3 + 2t + \frac{15}{t}\right)
\end{align}</math>
Since both sides are integers, <math>\frac{15}{t}</math> must be an integer, therefore ''t'' is a factor of 15, namely <math>t \in \{\pm 1, \pm 3, \pm 5, \pm 15\}</math>, therefore <math>k \in \{1, 3, 7, 57\}</math>. In turn:
Line 162 ⟶ 196:
* ''k'' = 3 and ''v'' = 10 yields the [[Petersen graph]],
* ''k'' = 7 and ''v'' = 50 yields the [[Hoffman–Singleton graph]], discovered by Hoffman and Singleton in the course of this analysis, and
* ''k'' = 57 and ''v'' = 3250 famously predicts a
| last = Dalfó | first = C.
| doi = 10.1016/j.laa.2018.12.035
Line 175 ⟶ 209:
}}</ref>
The Hoffman-Singleton theorem states that there are no
==See also==
Line 186 ⟶ 220:
==References==
* [[Andries Brouwer]] and Hendrik van Maldeghem (2022), ''Strongly Regular Graphs''. Cambridge: Cambridge University Press. {{isbn|1316512037}}. {{isbn|978-1316512036}}
* 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}}
| |||