Content deleted Content added
Quack5quack (talk | contribs) Rm hiding Tags: Mobile edit Mobile web edit Advanced mobile edit |
m →Geodetic graphs: Rm superfluous word. |
||
| (14 intermediate revisions by 6 users not shown) | |||
Line 7:
* every two non-adjacent vertices have {{math|μ}} common neighbours.
Such a strongly regular graph is denoted by {{math|srg(''v'', ''k'', λ, μ)}}
A strongly regular graph is a [[distance-regular graph]] with diameter 2 whenever μ is non-zero. It is a [[locally linear graph]] whenever {{math|1=λ = 1}}.
Line 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.
* 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).<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 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 52:
===Triangle-free graphs===
The strongly regular graphs with λ = 0 are [[triangle-free graph|triangle free]]. Apart from the complete graphs on fewer than 3 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 <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 93:
===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>
Line 101:
# 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 μ vertices in Level 1. Therefore the number of edges between Level 1 and Level 2 is <math>(v - k - 1)\mu</math>.
# 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 133 ⟶ 145:
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 144 ⟶ 156:
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>
Line 155 ⟶ 167:
* 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
===The Hoffman–Singleton theorem===
Line 162 ⟶ 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 184 ⟶ 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 197 ⟶ 209:
}}</ref>
The Hoffman-Singleton theorem states that there are no
==See also==
| |||