Content deleted Content added
Quack5quack (talk | contribs) →Examples: Evidently this was done fully without Sims. Tags: Mobile edit Mobile web edit Advanced mobile edit |
m →Geodetic graphs: Rm superfluous word. |
||
| (9 intermediate revisions by 5 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 41:
* [[Self-complementary graph|Self-complementary]] [[symmetric 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|''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 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==
| |||