Locally linear graph: Difference between revisions

Revision as of 07:24, 24 March 2025

Revision as of 07:26, 24 March 2025

Line 1:

{{Short description|Graph where every edge is in one triangle}}

[[File:33-duoprism graph.svg|thumb|The nine-vertex [[Paley graph]] is locally linear. Its six triangles are visible as equilateral triangles in this layout.]]

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. That is, locally (from the point of view of any one vertex) the rest of the graph looks like a [[perfect matching]].{{r|f}} Locally linear graphs have also been called locally matched graphs.{{r|lpv}} TheirMore technically, the triangles of any locally linear graph form the [[hyperedge]]s of a triangle-free 3-uniform linear [[hypergraph]]s, and they form the blocks of certain [[Steiner system|partial Steiner triple systems]],; and the locally linear graphs are exactly the [[Gaifman graph]]s of these hypergraphs or partial Steiner 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.