Content deleted Content added
distance-regular |
Better summary of article in linear |
||
Line 1:
[[File:Paley9-unique-triangle.svg|thumb|The nine-vertex [[Paley graph]] is locally linear. One of its six triangles is highlighted in green.]]
In [[graph theory]], a '''locally linear graph''' is an [[undirected graph]] in which the [[neighborhood (graph theory)|neighborhood]] of every [[vertex (graph theory)|vertex]] is an [[induced matching]]. That is, for every vertex <math>v</math>, every neighbor of <math>v</math> should be adjacent to exactly one other neighbor of <math>v</math>. Equivalently, every edge <math>uv</math> of such a graph belongs to a unique triangle <math>uvw</math>.{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}}
Examples of locally linear graphs include the [[triangular cactus graph]]s, the [[line graph]]s of 3-regular [[triangle-free graph]]s, and the [[Cartesian product of graphs|Cartesian products]] of smaller locally linear graphs. Certain [[Kneser graph]]s, and certain [[strongly regular graph]]s, are also locally linear.
Some locally linear graphs have a number of edges that is near-quadratic. The question of how dense these graphs can be is one of the formulations of the [[Ruzsa–Szemerédi problem]]. The densest [[planar graph]]s that can be locally linear are also known.
==Constructions and examples==
| |||