Content deleted Content added
→Algebraic constructions: elaborate Gaifman graph of 3-uniform linear hypergraph |
→top: partial Steiner triple systems |
||
Line 1:
{{Short description|Graph where every edge is in one triangle}}
[[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 exactly one triangle. Equivalently, for each vertex of the graph, its [[neighborhood (graph theory)|neighbors]] are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an [[induced matching]].{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}} They are exactly the [[Gaifman graph]]s of 3-uniform linear [[hypergraph]]s or of [[Steiner system|partial Steiner triple systems]].
Many constructions for locally linear graphs are known. 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.
| |||