Locally linear graph: Difference between revisions

Revision as of 07:39, 5 August 2021

Revision as of 07:41, 5 August 2021

Line 32:

==Regularity==

===Regular graphs with few vertices===

EveryA locallygraph linearis [[regular graph|regular]] mustwhen all of its vertices have eventhe same [[degree (graph theory)|degree]], the number of incident edges. Every locally linear graph must have even degree at each vertex, because the edges at each vertex can be paired up into triangles. The Cartesian product of two locally linear regular graphs is again locally linear and regular, with degree equal to the sum of the degrees of the factors. Therefore, one can take Cartesian products of locally linear graphs of degree two (triangles) to produce regular locally linear graphs of every even degree.{{r|f}}

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}}