Locally linear graph: Difference between revisions

Revision as of 04:48, 6 July 2021

Revision as of 23:44, 27 July 2021

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 every edge belongs to a unique triangle. Equivalently, for each vertex of the graph, the edges betweenits [[neighborhood (graph theory)|neighbors]] ofare theeach vertexadjacent pairto upexactly allone neighborsother into an [[induced matching]]neighbor, so thatthe eachneighbors neighborcan isbe adjacentpaired toup exactlyinto onean other[[induced neighbormatching]].{{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.