Locally linear graph: Difference between revisions

Revision as of 09:50, 3 April 2019

Revision as of 09:50, 3 April 2019

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 [[directedundirected 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.