Locally linear graph

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a locally linear graph is an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its <a href="/facts/Neighborhood_(graph_theory)/E6V1hk6b">neighbors</a> 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 <a href="/facts/Perfect_matching/LmtRYLgK">perfect matching</a>. Locally linear graphs have also been called locally matched graphs. More technically, the triangles of any locally linear graph form the <a href="/facts/Hyperedge/W0MqKkyE">hyperedges</a> of a triangle-free 3-uniform linear <a href="/facts/Hypergraph/qIR2o2I3">hypergraph</a>, and they form the blocks of certain <a href="/facts/Steiner_system/DdakpJpm">partial Steiner triple systems</a>; and the locally linear graphs are exactly the <a href="/facts/Gaifman_graph/qIR2o2I3">Gaifman graphs</a> of these hypergraphs or partial Steiner systems.
Many constructions for locally linear graphs are known. Examples of locally linear graphs include the <a href="/facts/Triangular_cactus_graph/s85ekIxz">triangular cactus graphs</a>, the <a href="/facts/Line_graph/RWNxSy5j">line graphs</a> of 3-regular <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free graphs</a>, and the <a href="/facts/Cartesian_product_of_graphs/wC4JJdyU">Cartesian products</a> of smaller locally linear graphs. Certain <a href="/facts/Kneser_graph/Iu0TVMKT">Kneser graphs</a>, and certain <a href="/facts/Strongly_regular_graph/0GbdLwSd">strongly regular graphs</a>, are also locally linear.
The question of how many edges locally linear graphs can have is one of the formulations of the <a href="/facts/Ruzsa%25E2%2580%2593Szemer%25C3%25A9di_problem/gjHJtwgF">Ruzsa–Szemerédi problem</a>. Although <a href="/facts/Dense_graph/xFC7b7s9">dense graphs</a> can have a number of edges proportional to the square of the number of vertices, locally linear graphs have a smaller number of edges, falling short of the square by at least a small non-constant factor. The densest <a href="/facts/Planar_graph/plREagr9">planar graphs</a> that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs.

Locally linear graph open-in-new

Locally linear graph