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 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. Locally linear graphs have also been called locally matched graphs. More technically, the triangles of any locally linear graph form the hyperedges of a triangle-free 3-uniform linear hypergraph, and they form the blocks of certain partial Steiner triple systems; and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems. Many constructions for locally linear graphs are known. Examples of locally linear graphs include the triangular cactus graphs, the line graphs of 3-regular triangle-free graphs, and the Cartesian products of smaller locally linear graphs. Certain Kneser graphs, and certain strongly regular graphs, 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 dense graphs 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 planar graphs that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs.
Constructions
Gluing and products
The friendship graphs, graphs formed by gluing together a collection of triangles at a single shared vertex, are locally linear. They are the only finite graphs having the stronger property that every pair of vertices (adjacent or not) share exactly one common neighbor. More generally every triangular cactus graph, a graph formed by gluing triangles at shared vertices without forming any additional cycles, is locally linear. Locally linear graphs may be formed from smaller locally linear graphs by the following operation, a form of the clique-sum operation on graphs. Let G {\displaystyle G} and H {\displaystyle H} be any two locally linear graphs, select a triangle from each of them, and glue the two graphs by merging together corresponding pairs of vertices in the two selected triangles. Then the resulting graph remains locally linear. The Cartesian product of any two locally linear graphs remains locally linear, because any triangles in the product come from triangles in one or the other factors. For instance, the nine-vertex Paley graph (the graph of the 3-3 duoprism) is the Cartesian product of two triangles. The Hamming graph H ( d , 3 ) {\displaystyle H(d,3)} is a Cartesian product of d {\displaystyle d} triangles, and again is locally linear.
From smaller graphs Some graphs that are not themselves locally linear can be used as a framework to construct larger locally linear graphs. One such construction involves line graphs. For any graph G {\displaystyle G} , the line graph L ( G ) {\displaystyle L(G)} is a graph that has a vertex for every edge of G {\displaystyle G} . Two vertices in L ( G ) {\displaystyle L(G)} are adjacent when the two edges that they represent in G {\displaystyle G} have a common endpoint. If G {\displaystyle G} is a 3-regular triangle-free graph, then its line graph L ( G ) {\displaystyle L(G)} is 4-regular and locally linear. It has a triangle for every vertex v {\displaystyle v} of G {\displaystyle G} , with the vertices of the triangle corresponding to the three edges incident to v {\displaystyle v} . Every 4-regular locally linear graph can be constructed in this way. For instance, the graph of the cuboctahedron is the line graph of a cube, so it is locally linear. The locally linear nine-vertex Paley graph, constructed above as a Cartesian product, may also be constructed in a different way as the line graph of the utility graph K 3 , 3 {\displaystyle K_{3,3}} . The line graph of the Petersen graph is also locally linear by this construction. It has a property analogous to the cages: it is the smallest possible graph in which the largest clique has three vertices, each vertex is in exactly two edge-disjoint cliques, and the shortest cycle with edges from distinct cliques has length five.
… excerpt ends here. Continue reading the full article.
