locally linear graph

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, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs.

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$ and $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)$ is a Cartesian product of $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$, the line graph $L(G)$ is a graph that has a vertex for every edge of $G$. Two vertices in $L(G)$ are adjacent when the two edges that they represent in $G$ have a common endpoint. If $G$ is a 3-regular triangle-free graph, then its line graph $L(G)$ is 4-regular and locally linear. It has a triangle for every vertex $v$ of $G$, with the vertices of the triangle corresponding to the three edges incident to $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_$. 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.

A more complicated expansion process applies to planar graphs. Let $G$ be a planar graph embedded in the plane in such a way that every face is a quadrilateral, such as the graph of a cube. Gluing a square antiprism onto each face of $G$, and then deleting the original edges of $G$, produces a new locally linear planar graph. The numbers of edges and vertices of the result can be calculated from Euler's polyhedral formula: if $G$ has $n$ vertices, it has exactly $n-2$ faces, and the result of replacing the faces of $G$ by antiprisms has $5(n-2)+2$ vertices and $12(n-2)$ edges. For instance, the cuboctahedron can again be produced in this way, from the two faces (the interior and exterior) of a 4-cycle.
The removed 4-cycle of this construction can be seen on the cuboctahedron as a cycle of four diagonals of its square faces, bisecting the polyhedron.

Algebraic constructions

Certain Kneser graphs, graphs constructed from the intersection patterns of equal-size sets, are locally linear. Kneser graphs are described by two parameters, the size of the sets they represent and the size of the universe from which these sets are drawn. The Kneser graph $KG_$ has $\tbinom$ vertices (in the standard notation for binomial coefficients), representing the $b$-element subsets of an $a$-element set. In this graph, two vertices are adjacent when the corresponding subsets are disjoint sets, having no elements in common. In the special case when $a=3b$, the resulting graph is locally linear, because for each two disjoint $b$-element subsets $X$ and $Y$ there is exactly one other $b$-element subset disjoint from both of them, consisting of all the elements that are neither in $X$ nor in $Y$. The resulting locally linear graph has $\tbinom$ vertices and $\tfrac\tbinom\tbinom$ edges. For instance, for $b=2$ the Kneser graph $KG_$ is locally linear with 15 vertices and 45 edges.

Locally linear graphs can also be constructed from progression-free sets of numbers.
Let $p$ be a prime number, and let $A$ be a subset of the numbers modulo $p$ such that no three members of $A$ form an arithmetic progression modulo $p$. (That is, $A$ is a Salem–Spencer set modulo $p$.) This set can be used to construct a tripartite graph with $3p$ vertices and $3p\cdot, A,$ edges that is locally linear. To construct this graph, make three sets of vertices, each numbered from $0$ to $p-1$. For each number $x$ in the range from $0$ to $p-1$ and each element $a$ of $A$, construct a triangle connecting the vertex with number $x$ in the first set of vertices, the vertex with number $x+a$ in the second set of vertices, and the vertex with number $x+2a$ in the third set of vertices. Form a graph as the union of all of these triangles. Because it is a union of triangles, every edge of the resulting graph belongs to a triangle. However, there can be no other triangles than the ones formed in this way. Any other triangle would have vertices numbered $(x,x+a,x+a+b)$ where $a$, $b$, and $c=(a+b)/2$ all belong to $A$, violating the assumption that there be no arithmetic progressions $(a,c,b)$ in $A$. For example, with $p=3$ and $A=\$, the result of this construction is the nine-vertex Paley graph.

Regularity

Regular graphs with few vertices

A graph is regular when all of its vertices have the same degree, the number of incident edges. Every locally linear graph must have even degree at each vertex, because the edges at each vertex can be paired up into triangles. The Cartesian product of two locally linear regular graphs is again locally linear and regular, with degree equal to the sum of the degrees of the factors. Therefore, one can take Cartesian products of locally linear graphs of degree two (triangles) to produce regular locally linear graphs of every even degree.

The $2r$-regular locally linear graphs must have at least $6r-3$ vertices, because there are this many vertices among any triangle and its neighbors alone. (No two vertices of the triangle can share a neighbor without violating local linearity.) Regular graphs with exactly this many vertices are possible only when $r$ is 1, 2, 3, or 5, and are uniquely defined for each of these four cases. The four regular graphs meeting this bound on the number of vertices are the 3-vertex 2-regular triangle $K_3$, the 9-vertex 4-regular Paley graph, the 15-vertex 6-regular Kneser graph $KG_$, and the 27-vertex 10-regular complement graph of the Schläfli graph. The final 27-vertex 10-regular graph also represents the intersection graph of the 27 lines on a cubic surface.

Strongly regular graphs

A strongly regular graph can be characterized by a quadruple of parameters $(n,k,\lambda,\mu)$ where $n$ is the number of vertices, $k$ is the number of incident edges per vertex, $\lambda$ is the number of shared neighbors for every adjacent pair of vertices, and $\mu$ is the number of shared neighbors for every non-adjacent pair of vertices. When $\lambda=1$ the graph is locally linear. The locally linear graphs already mentioned above that are strongly regular graphs and their parameters are
*the triangle (3,2,1,0),
*the nine-vertex Paley graph (9,4,1,2),
*the Kneser graph $KG_$ (15,6,1,3), and
*the complement of the Schläfli graph (27,10,1,5).
Other locally linear strongly regular graphs include
*the Brouwer–Haemers graph (81,20,1,6),
*the Berlekamp–van Lint–Seidel graph (243,22,1,2),
*the Cossidente–Penttila graph (378,52,1,8), and
*the Games graph (729,112,1,20).
Other potentially-valid combinations with $\lambda=1$ include (99,14,1,2) and (115,18,1,3) but it is unknown whether strongly regular graphs with those parameters exist. The question of the existence of a strongly regular graph with parameters (99,14,1,2) is known as Conway's 99-graph problem, and John Horton Conway has offered a $1000 prize for its solution.

Distance-regular graphs

There are finitely many distance-regular graphs of degree 4 or 6 that are locally linear. Beyond the strongly regular graphs of the same degrees, they also include the line graph of the Petersen graph, the Hamming graph $H(3,3)$, and the halved Foster graph.

Density

One formulation of the Ruzsa–Szemerédi problem asks for the maximum number of edges in an $n$-vertex locally linear graph. As Imre Z. Ruzsa and Endre Szemerédi proved, this maximum number is $o(n^2)$ but is $\Omega(n^)$ for every $\varepsilon>0$. The construction of locally linear graphs from progression-free sets leads to the densest known locally linear graphs, with $n^2/\exp O(\sqrt)$ edges. (In these formulas, $o$, $\Omega$, and $O$ are examples of little o notation, big Omega notation, and big O notation, respectively.)

Among planar graphs, the maximum number of edges in a locally linear graph with $n$ vertices is $\tfrac(n-2)$. The graph of the cuboctahedron is the first in an infinite sequence of polyhedral graphs with $n=5k+2$ vertices and $\tfrac(n-2)=12k$ edges, for $k=2,3,\dots$, constructed by expanding the quadrilateral faces of $K_$ into antiprisms. These examples show that the $\tfrac(n-2)$ upper bound can be attained.

Every locally linear graph has the property that it remains connected after any matching is removed from it, because in any path through the graph, each matched edge can be replaced by the other two edges of its triangle. Among the graphs with this property, the least dense are the triangular cactus graphs, which are also the least dense locally linear graphs.

References

{{reflist, refs=

{{citation
, last1 = Brouwer , first1 = A. E. , author1-link = Andries Brouwer
, last2 = Haemers , first2 = W. H.
, department = A collection of contributions in honour of Jack van Lint
, doi = 10.1016/0012-365X(92)90532-K
, journal = Discrete Mathematics
, mr = 1181899
, pages = 77–82
, title = Structure and uniqueness of the (81,20,1,6) strongly regular graph
, volume = 106/107
, year = 1992, doi-access = free

{{citation
, last1 = Bondarenko , first1 = Andriy V.
, last2 = Radchenko , first2 = Danylo V.
, doi = 10.1016/j.jctb.2013.05.005
, issue = 4
, journal = Journal of Combinatorial Theory
, mr = 3071380
, pages = 521–531
, series = Series B
, title = On a family of strongly regular graphs with $\lambda=1$
, volume = 103
, year = 2013, arxiv = 1201.0383

{{citation
, last1 = Cossidente , first1 = Antonio
, last2 = Penttila , first2 = Tim
, doi = 10.1112/S0024610705006964
, issue = 3
, journal = Journal of the London Mathematical Society
, mr = 2190334
, pages = 731–741
, series = Second Series
, title = Hemisystems on the Hermitian surface
, volume = 72
, year = 2005

{{citation
, last1 = Devillers , first1 = Alice
, last2 = Jin , first2 = Wei
, last3 = Li , first3 = Cai Heng
, last4 = Praeger , first4 = Cheryl E. , author4-link = Cheryl Praeger
, doi = 10.1016/j.jcta.2012.10.004
, issue = 2
, journal = Journal of Combinatorial Theory
, mr = 2995054
, pages = 500–508
, series = Series A
, title = Local 2-geodesic transitivity and clique graphs
, volume = 120
, year = 2013, doi-access = free
. In the notation of this reference, the family of $2r$-regular graphs is denoted as $F(r,2)$.

{{citation
, last1 = Erdős , first1 = Paul , author1-link = Paul Erdős
, last2 = Rényi , first2 = Alfréd , author2-link = Alfréd Rényi
, last3 = Sós , first3 = Vera T. , author3-link = Vera T. Sós
, journal = Studia Sci. Math. Hungar.
, pages = 215–235
, title = On a problem of graph theory
, url = https://www.renyi.hu/~p_erdos/1966-06.pdf
, volume = 1
, year = 1966

{{citation
, last1 = Berlekamp , first1 = E. R. , author1-link = Elwyn Berlekamp
, last2 = van Lint , first2 = J. H. , author2-link = J. H. van Lint
, last3 = Seidel , first3 = J. J.
, doi = 10.1016/B978-0-7204-2262-7.50008-9
, journal = A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)
, mr = 0364015
, pages = 25–30
, publisher = North-Holland , location = Amsterdam
, title = A strongly regular graph derived from the perfect ternary Golay code
, year = 1973, isbn = 9780720422627 , url = https://research.tue.nl/nl/publications/a-strongly-regular-graph-derived-from-the-perfect-ternary-golay-code(10db0cd0-72b4-4d07-bc44-83d07d86e7f0).html

{{citation
, last = Fronček , first = Dalibor
, hdl = 10338.dmlcz/136481 , hdl-access = free
, issue = 1
, journal = Mathematica Slovaca
, mr = 1016323
, pages = 3–6
, title = Locally linear graphs
, volume = 39
, year = 1989

{{citation
, last = Fan , first = Cong
, doi = 10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M
, issue = 1
, journal = Journal of Graph Theory
, mr = 1402135
, pages = 21–31
, title = On generalized cages
, volume = 23
, year = 1996

{{citation
, last1 = Farley , first1 = Arthur M.
, last2 = Proskurowski , first2 = Andrzej
, doi = 10.1002/net.3230120404
, issue = 4
, journal = Networks
, mr = 686540
, pages = 393–403
, title = Networks immune to isolated line failures
, volume = 12
, year = 1982; see in particular p. 397: "We call the resultant network a triangle cactus; it is a cactus network in which every line belongs to exactly one triangle."

{{citation
, last1 = Hiraki , first1 = Akira
, last2 = Nomura , first2 = Kazumasa
, last3 = Suzuki , first3 = Hiroshi
, doi = 10.1023/A:1008776031839
, issue = 2
, journal = Journal of Algebraic Combinatorics
, mr = 1761910
, pages = 101–134
, title = Distance-regular graphs of valency 6 and $a_1=1$
, volume = 11
, year = 2000, doi-access = free

{{citation
, last1 = Larrión , first1 = F.
, last2 = Pizaña , first2 = M. A.
, last3 = Villarroel-Flores , first3 = R.
, journal = Ars Combinatoria
, mr = 2867738
, pages = 385–391
, title = Small locally {{math, ''nK''₂ graphs
, url = http://xamanek.izt.uam.mx/map/papers/locallynk5w.pdf
, volume = 102
, year = 2011

{{citation
, last = Makhnëv , first = A. A.
, doi = 10.1007/BF01158426
, issue = 5
, journal = Akademiya Nauk SSSR
, mr = 980587
, pages = 667–672, 702
, title = Strongly regular graphs with $\lambda=1$
, volume = 44
, year = 1988, s2cid = 120911900

{{citation
, last = Munaro , first = Andrea
, doi = 10.1016/j.disc.2017.01.006
, issue = 6
, journal = Discrete Mathematics
, mr = 3624607
, pages = 1210–1226
, title = On line graphs of subcubic triangle-free graphs
, volume = 340
, year = 2017, url = https://pure.qub.ac.uk/en/publications/on-line-graphs-of-subcubic-trianglefree-graphs(aa6963d5-59e6-4d92-a9d6-d89d4374396c).html

{{citation
, last1 = Ruzsa , first1 = I. Z. , author1-link = Imre Z. Ruzsa
, last2 = Szemerédi , first2 = E. , author2-link = Endre Szemerédi
, contribution = Triple systems with no six points carrying three triangles
, mr = 519318
, pages = 939–945
, publisher = North-Holland , location = Amsterdam and New York
, series = Colloq. Math. Soc. János Bolyai
, title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II
, volume = 18
, year = 1978

{{citation
, last = Zelinka , first = Bohdan
, hdl = 10338.dmlcz/133017 , hdl-access = free
, issue = 2
, journal = Mathematica Slovaca
, mr = 945363
, pages = 99–103
, title = Polytopic locally linear graphs
, volume = 38
, year = 1988

{{citation
, last1 = Zehavi , first1 = Sa'ar
, last2 = Oliveira , first2 = Ivo Fagundes David
, arxiv = 1707.08047
, title = Not Conway's 99-graph problem
, year = 2017

Graph families