Content deleted Content added
Line 26:
Every locally linear graph must have even [[degree (graph theory)|degree]] at each vertex, because the edges at each vertex can be paired up into triangles. The <math>2r</math>-regular locally linear graphs must have at least <math>6r-3</math> vertices, because there are this many vertices among any triangle and its neighbors alone. (No two vertices of the triangle can share a neighbor without violating local linearity.) Regular graphs with exactly this many vertices are possible only when <math>r</math> is 1, 2, 3, or 5, and are uniquely defined for each of these four cases. The four regular graphs meeting this bound on the number of vertices are the 3-vertex 2-regular triangle <math>K_3</math>, the 9-vertex 4-regular Paley graph, the 15-vertex 6-regular Kneser graph <math>KG_{6,2}</math>, and the 27-vertex 10-regular [[complement graph]] of the [[Schläfli graph]]. The final 27-vertex 10-regular graph also represents the [[intersection graph]] of the 27 lines on a [[cubic surface]].{{r|lpv}}
A [[strongly regular graph]] can be characterized by a quadruple of parameters <math>(n,k,\lambda,\mu)</math> where <math>n</math> is the number of vertices, <math>k</math> is the number of incident edges per vertex, <math>\lambda</math> is the number of shared neighbors for every adjacent pair of vertices, and <math>\mu</math> is the number of shared neighbors for every non-adjacent pair of vertices. When <math>\lambda=1</math> the graph is locally linear. The
*the triangle (3,2,1,0),
*the nine-vertex Paley graph (9,4,1,2),
*the Kneser graph <math>KG_{6,2}</math> (15,6,1,3), and
*the complement of the Schläfli graph (27,10,1,5).
Other locally linear strongly regular graphs include
*the [[Brouwer–Haemers graph]] (81,20,1,6),{{r|bh}}
*the [[Berlekamp–van Lint–Seidel graph]] (243,22,1,2),{{r|evls}}
| |||