Locally linear graph: Difference between revisions

Revision as of 07:18, 5 August 2021

Revision as of 07:22, 5 August 2021

Line 3:

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}}

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.

The question of how many edges locally linear graphs can have is one of the formulations of the [[Ruzsa–Szemerédi problem]]. Although this[[dense graph]]s can have a number of edges canproportional beto nearlythe quadraticsquare of the number of vertices, itlocally mustlinear fallgraphs have a smaller number of edges, falling short of quadraticthe square by at least a small non-constant factor. The densest [[planar graph]]s that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs.

==Constructions==