Strongly regular graph: Difference between revisions

Revision as of 17:45, 1 June 2022

Revision as of 17:55, 10 June 2022

Line 6:

* Every two [[adjacent vertices]] have λ common neighbours.

* Every two non-adjacent vertices have μ common neighbours.

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>

Some authors exclude graphs which satisfy the definition trivially, namely those graphs which are the disjoint union of one or more equal-sized [[complete graph]]s,<ref>[http://homepages.cwi.nl/~aeb/math/ipm.pdf Brouwer, Andries E; Haemers, Willem H. ''Spectra of Graphs''. p. 101] {{Webarchive|url=https://web.archive.org/web/20120316102909/http://homepages.cwi.nl/~aeb/math/ipm.pdf |date=2012-03-16 }}</ref><ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag New York, 2001, p. 218.</ref> and their [[complement graph|complements]], the complete [[multipartite graph]]s with equal-sized independent sets.

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'' + λ)}}.

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}}.

==Etymology==

SomeA authorsstrongly excluderegular graph is denoted an srg(''v'', ''k'', λ, μ) in the literature. By convention, graphs which satisfy the definition trivially, namelyare thoseexcluded from detailed studies and lists of strongly regular graphs. whichThese areinclude the disjoint union of one or more equal-sized [[complete graph]]s,<ref>[http://homepages.cwi.nl/~aeb/math/ipm.pdf Brouwer, Andries E; Haemers, Willem H. ''Spectra of Graphs''. p. 101] {{Webarchive|url=https://web.archive.org/web/20120316102909/http://homepages.cwi.nl/~aeb/math/ipm.pdf |date=2012-03-16 }}</ref><ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag New York, 2001, p. 218.</ref> and their [[complement graph|complements]], the complete [[multipartite graph]]s 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 (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==

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> They built upon earlier work in the 1950s in the then-new field of [[spectral graph theory]].

==Examples==

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]]. It is not possible for such a graph to have <math>\lambda = 1</math>, but otherOther 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 <math>\mu=1</math> would have,<ref>{{citation

| 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==

Line 116 ⟶ 120:

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 ''lp'' (not to be confused with <math>\lambda</math> the graph parameter) and substitute <math>Ax = lxpx</math>, <math>Jx = 0</math> and <math>Ix = x</math>:

:<math>lp^2 x = kx + \lambda l x - \mu x - \mu l x</math>

Eliminate x and rearrange to get a quadratic:

:<math>lp^2 + (\mu - \lambda ) l - (k - \mu) = 0</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 ⟶ 129:

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'' of 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 ⟶ 142:

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:

* <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 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-existence [https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html here] with reasons for non-existence if any.

===The Hoffman–Singleton theorem===

Line 186 ⟶ 206:

==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}}