Strongly regular graph: Difference between revisions

Revision as of 10:11, 6 July 2021

Revision as of 19:37, 28 October 2021

Line 11:

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−kv''−1 − ''k'' − 1, ''v''−2−2 − 2 − 2''k'' + μ, ''v''−2 − 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}}.

It is a [[locally linear graph]] whenever λ=1.

==Properties==

===Relationship between Parametersparameters===

The four parameters in an srg(''v'', ''k'', λ, μ) are not independent and must obey the following relation:

:<math>(v - k - 1)\mu = k(k - \lambda - 1)</math>

The above relation can be derived very easily 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 nodes in Level 2. Therefore, there are <math>k\times (k - \lambda - 1)</math> 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 <math>(v - k - 1)</math> 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 <math>(v - k - 1)\times\mu</math>.

# Equating the two expressions for the edges between Level 1 and Level 2, the relation follows.

===Adjacency Matrixmatrix===

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:

:<math>AJ = JA = kJ,</math>

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,

:<math>{A}^{2} = k{I}kI + \lambda{A} + \mu({J - I - A})</math>

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.

Line 40:

===Eigenvalues===

The adjacency matrix of the graph has exactly three [[eigenvalue]]s:

* ''k'', whose [[Multiplicity (mathematics)|multiplicity]] is 1 (as seen above)

* <math>\frac{1}{2}\left[(\lambda - \mu) + \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right],</math> whose multiplicity is <math>\frac{1}{2} \left[(v - 1) - \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]</math>

* <math>\frac{1}{2}\left[(\lambda - \mu) - \sqrt{(\lambda - \mu)^2 + 4(k-\mu)}\,\right],</math> whose multiplicity is <math>\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 ''λ'', related to the so-called ''Krein conditions''.

Strongly regular graphs for which <math>2k + (v - 1)(\lambda - \mu) \ne 0</math> have integer eigenvalues with unequal multiplicities.

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>\textoperatorname{srg}\bigleft(v, \tfracfrac{1}{2}(v - 1), \tfracfrac{1}{4}(v - 5), \tfracfrac{1}{4}(v - 1)\bigright).</math>

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>

Line 57:

* 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''&nbsp;×&nbsp;''n'' square [[rook's graph]], i.e., the line graph of a balanced complete bipartite graph ''K''_''n'',''n'''', is an srg(''n''², 2''n''&nbsp;−&nbsp;2, ''n''&nbsp;−&nbsp;2, 2). The parameters for {{nowrap|''n'' {{=}} 4}} coincide with those of the Shrikhande graph, but the two graphs are not isomorphic.

* The [[line graph]] of a complete graph ''K_n'' is an srg(<math display="inline">\operatorname{srg}\left(\binom{n}{2}, 2(n - 2), n - 2, 4\right)</math>).

* The [[Chang graphs]] are srg(28, 12, 6, 4), the same as the line graph of ''K''₈, but these four graphs are not isomorphic.

* The [[line graph]] of a [[generalized quadrangle]] 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]] is an srg(27, 16, 10, 8).<ref>{{MathWorld | urlname=SchlaefliGraph | title=Schläfli graph|mode=cs2}}</ref>

* The [[Hoffman–Singleton graph]] is an srg(50, 7, 0, 1).

Line 71:

* 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''&nbsp;−&nbsp;1)/2, (''q''&nbsp;−&nbsp;5)/4, (''q''&nbsp;−&nbsp;1)/4). The smallest Paley graph, with {{nowrap|''q'' {{=}} 5}}, is the 5-cycle (above).

* [[Self-complementary graph|self-complementary]] [[Symmetricsymmetric graph|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 {{nowrap|μ {{=}} 0}} or {{nowrap|λ {{=}} ''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.<ref>{{citation

Line 81:

| publisher = Online Encyclopedia of Integer Sequences

| title = Five $1,000 Problems (Update 2017)

| url = https://oeis.org/A248380/a248380.pdf
}}</ref>

===Triangle-free graphs, Moore graphs, and geodetic graphs===

Line 92 ⟶ 93:

| title = A survey on the missing Moore graph

| volume = 569

| year = 2019 | hdl = 2117/127212

| hdl-access = free

}}</ref>

More generally, 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|unweighted shortest path]].<ref name=bb>{{citation

| last1 = Blokhuis | first1 = A.

| last2 = Brouwer | first2 = A. E. | authorlink = Andries Brouwer

Line 106 ⟶ 107:

| title = Geodetic graphs of diameter two

| volume = 25

| year = 1988

| year = 1988}}</ref> The only known strongly regular graphs with <math>\mu = 1</math> are the Moore graphs. It is not possible for such a graph to have <math>\lambda = 1</math>, 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 <math>\mu=1</math> would have,<ref>{{citation

| last1 = Deutsch | first1 = J.

| last2 = Fisher | first2 = P. H.

Line 117 ⟶ 119:

| volume = 22

| year = 2001| doi-access = free

}}</ref><ref>{{citation

| last1 = Belousov | first1 = I. N.

| last2 = Makhnev | first2 = A. A.

Line 126 ⟶ 128:

| title = On strongly regular graphs with <math>\mu=1</math> and their automorphisms

| volume = 410

| year = 2006
}}</ref> it is not known whether any more exist or even whether their number is finite.<ref name=bb/>

==See also==