Content deleted Content added
Correct assertion about non-primitive strongly regular graphs |
m →Geodetic graphs: Rm superfluous word. |
||
| (3 intermediate revisions by the same user not shown) | |||
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 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 209:
}}</ref>
The Hoffman-Singleton theorem states that there are no
==See also==
| |||