Locally linear graph: Difference between revisions

Revision as of 02:20, 13 February 2019

Revision as of 04:25, 13 February 2019

Line 24:

===Regular and strongly regular graphs===

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 neighborsvertices 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 known locally linear strongly regular graphs and their parameters already mentioned include