Locally linear graph: Difference between revisions

Revision as of 23:44, 27 July 2021

Revision as of 23:46, 27 July 2021

Line 4:

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 densemany edges locally linear graphs can be (how many edges they can have, relative to the total number of pairs of vertices) is one of the formulations of the [[Ruzsa–Szemerédi problem]]. SomeAlthough locally linear graphs have athis number of edges thatcan isbe withinnearly a smallquadratic, butit non-constant,must factorfall short of thequadratic numberby ofa vertexsmall pairs.non-constant factor. The densest [[planar graph]]s that can be locally linear are also known.

==Constructions==