Locally Linear Graph
   HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a locally linear graph is an
undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
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 In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
. Locally linear graphs have also been called locally matched graphs. More technically, the triangles of any locally linear graph form the
hyperedge This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...
s of a triangle-free 3-uniform linear
hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
, 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 graph In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ( ...
s, the
line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
s of 3-regular
triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
s, and the Cartesian products of smaller locally linear graphs. Certain
Kneser graph Kneser is a surname. Notable people with the surname include: * Adolf Kneser (1862–1930), mathematician * Hellmuth Kneser (1898–1973), mathematician, son of Adolf Kneser * Martin Kneser (1928–2004), mathematician, son of Hellm ...
s, and certain
strongly regular graph In graph theory, a strongly regular graph (SRG) is a regular graph with vertices and degree such that for some given integers \lambda, \mu \ge 0 * every two adjacent vertices have common neighbours, and * every two non-adjacent vertices h ...
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 In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number ...
. Although
dense graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinctio ...
s 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 graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s 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 graph In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or -fan) is a planar, undirected graph with vertices and edges. The friendship graph can be constructed by joining copies of the cycle graph with a ...
s, 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 In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ( ...
, 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 In graph theory, a branch of mathematics, a clique sum (or clique-sum) is a way of combining two graphs by gluing them together at a clique (graph theory), clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' ...
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 In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is A\times B = \. A table c ...
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 In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yiel ...
(the graph of the
3-3 duoprism In the geometry of 4 dimensions, the 3-3 duoprism or triangular duoprism is a four-dimensional convex polytope. Descriptions The duoprism is a 4-polytope that can be constructed using Cartesian product of two polygons. In the case of 3-3 duopr ...
) is the Cartesian product of two triangles. The
Hamming graph Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , ...
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 graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
s. 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 In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
, 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 A cuboctahedron is a polyhedron with 8 triangular faces and 6 square faces. A cuboctahedron has 12 identical vertex (geometry), vertices, with 2 triangles and 2 squares meeting at each, and 24 identical edge (geometry), edges, each separating a tr ...
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 In economics, utility is a measure of a certain person's satisfaction from a certain state of the world. Over time, the term has been used with at least two meanings. * In a normative context, utility refers to a goal or objective that we wish ...
K_. The line graph of the
Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph i ...
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 A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
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 graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s. 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 In geometry, the square antiprism is the second in an infinite family of antiprisms formed by an even number, even-numbered sequence of triangle sides closed by two polygon caps. It is also known as an ''anticube''. If all its faces are regular ...
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 In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's ...
: 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 graph Kneser is a surname. Notable people with the surname include: * Adolf Kneser (1862–1930), mathematician * Hellmuth Kneser (1898–1973), mathematician, son of Adolf Kneser * Martin Kneser (1928–2004), mathematician, son of Hellm ...
s, 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 K G_ has \tbinom vertices (in the standard notation for
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s), representing the b-element subsets of an a-element set. In this graph, two vertices are adjacent when the corresponding subsets are
disjoint set In set theory in mathematics and formal logic, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' wh ...
s, 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 An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
modulo p. (That is, A is a
Salem–Spencer set In mathematics, and in particular in arithmetic combinatorics, a Salem-Spencer set is a set of numbers no three of which form an arithmetic progression. Salem–Spencer sets are also called 3-AP-free sequences or progression-free sets. They have ...
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. The triangles in a locally linear graph can be equivalently thought of as forming a 3-uniform
hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...
. Such a hypergraph must be linear, meaning that no two of its hyperedges (the triangles) can share more than one vertex. The locally linear graph itself is the Gaifman graph of the hypergraph, the graph of pairs of vertices that belong to a common hyperedge. In this view it makes sense to talk about the
girth Girth may refer to: Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...
of the hypergraph. In graph terms, this is the length of the shortest cycle that is not one of the triangles of the graph. An algebraic construction based on polarity graphs (also called Brown graphs) has been used, in this context, to find dense locally linear graphs that have no 4-cycles; their hypergraph girth is five. A polarity graph is defined from a
finite projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane (geometry), plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines (namely, paral ...
, and a
polarity Polarity may refer to: Science *Electrical polarity, direction of electrical current *Polarity (mutual inductance), the relationship between components such as transformer windings *Polarity (projective geometry), in mathematics, a duality of orde ...
, an incidence-preserving bijection between its points and its lines. The vertices of the polarity graph are points, and an edge connects two points whenever one is polar to a line containing the other. More algebraically, the vertices of the same graph can be represented by homogeneous coordinates: these are triples of values (x,y,z) from a
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, not all zero, where two triples define the same point in the plane whenever they are scalar multiples of each other. Two points, represented by triples in this way, are adjacent when their
inner product In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, ofte ...
is zero. The polarity graph for a finite field of odd order q has q^2+q+1 vertices, of which q+1 are self-adjacent and do not belong to any triangles. When these are removed, the result is a locally linear graph with q^2 vertices, \bigl(\tfrac12+o(1)\bigr)q^3 edges, and hypergraph girth five, giving the maximum possible number of edges for a locally linear graph of this girth up to lower-order terms.


Regularity


Regular graphs with few vertices

A graph is
regular Regular may refer to: Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instruments, tunings with equal intervals between the paired notes of successive open strings Other uses * Regular character, ...
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 In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
of the
Schläfli graph In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16- regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8). ...
. The final 27-vertex 10-regular graph also represents the
intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of the 27 lines on a
cubic surface In mathematics, a cubic surface is a surface in 3-dimensional space defined by one polynomial equation of degree 3. Cubic surfaces are fundamental examples in algebraic geometry. The theory is simplified by working in projective space rather than ...
.


Strongly regular graphs

A
strongly regular graph In graph theory, a strongly regular graph (SRG) is a regular graph with vertices and degree such that for some given integers \lambda, \mu \ge 0 * every two adjacent vertices have common neighbours, and * every two non-adjacent vertices h ...
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 In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20- regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construc ...
(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 In graph theory, the Games graph is the largest known locally linear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1,20). This means that it has 729 vertices, and 40824 edges (112 per vertex). Each edge is in a u ...
(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 In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices ...
, and
John Horton Conway John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician. He was active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many b ...
has offered a $1000 prize for its solution.


Distance-regular graphs

There are finitely many
distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...
s 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 In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges. The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is a ...
.


Density

One formulation of the
Ruzsa–Szemerédi problem In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number ...
asks for the maximum number of edges in an n-vertex locally linear graph. As
Imre Z. Ruzsa Imre Z. Ruzsa (born 23 July 1953) is a Hungarian mathematician specializing in number theory. Life He graduated from the Eötvös Loránd University in 1976. Since then he has been at the Alfréd Rényi Institute of Mathematics of the Hungarian ...
and
Endre Szemerédi Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and computer scientist, working in the field of combinatorics and theoretical computer science. He has been the State of New Jersey Professor of computer science a ...
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 ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul ...
,
big Omega notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul ...
, and
big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
, respectively.) Among
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, the maximum number of edges in a locally linear graph with n vertices is \tfrac(n-2). The graph of the
cuboctahedron A cuboctahedron is a polyhedron with 8 triangular faces and 6 square faces. A cuboctahedron has 12 identical vertex (geometry), vertices, with 2 triangles and 2 squares meeting at each, and 24 identical edge (geometry), edges, each separating a tr ...
is the first in an infinite sequence of
polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...
s 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.


Applications

One application of locally linear graphs occurs in the formulation of Greechie diagrams, which are used in
quantum logic In the mathematical study of logic and the physical analysis of quantum foundations, quantum logic is a set of rules for manip­ulation of propositions inspired by the structure of quantum theory. The formal system takes as its starting p ...
to help determine whether certain
Hilbert space In mathematics, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
equations can be inferred from each other. In this application, the triangles of locally linear graphs form the blocks of Greechie diagrams with block size three. The Greechie diagrams corresponding to lattices come from the locally linear graphs of hypergraph girth five or more, as constructed for instance from polarity graphs. A combination of random sampling and a
graph removal lemma In graph theory, the graph removal lemma states that when a graph contains few copies of a given Subgraph (graph theory), subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph ...
can be used to find large high-girth 3-uniform hypergraphs within arbitrary 3-uniform linear hypergraphs or partial Steiner triple systems. This method can then be used to prove asymptotically tight lower bounds on the
independence number Independence is a condition of a nation, country, or state, in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the status of a ...
of 3-uniform linear hypergraphs and partial Steiner triple systems.


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 Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
, 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 =
{{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 The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...
, 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 The London Mathematical Society (LMS) is one of the United Kingdom's learned societies for mathematics (the others being the Royal Statistical Society (RSS), the Institute of Mathematics and its Applications (IMA), the Edinburgh Mathematical S ...
, 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 The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...
, 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 = Henning , first1 = Michael A. , last2 = Yeo , first2 = Anders , contribution = Chapter 12: Partial Steiner triple systems , doi = 10.1007/978-3-030-46559-9_12 , isbn = 978-3-030-46559-9 , mr = 4180641 , pages = 171–177 , publisher = Springer , location = Cham , series = Developments in Mathematics , title = Transversals in Linear Uniform Hypergraphs , volume = 63 , year = 2020 {{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''2 graphs , url = http://xamanek.izt.uam.mx/map/papers/locallynk5w.pdf , volume = 102 , year = 2011 {{citation , last1 = Lazebnik , first1 = Felix , last2 = Verstraëte , first2 = Jacques , doi = 10.37236/1718 , doi-access = free , journal =
Electronic Journal of Combinatorics The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Geor ...
, mr = 2014512 , page = R25:1–R25:15 , title = On hypergraphs of girth five , volume = 10 , year = 2003
{{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 , last1 = McKay , first1 = Brendan D. , author1-link = Brendan McKay (mathematician) , last2 = Megill , first2 = Norman D. , last3 = Pavičić , first3 = Mladen , doi = 10.1023/A:1026476701774 , issue = 10 , journal = International Journal of Theoretical Physics , mr = 1803695 , pages = 2381–2406 , title = Algorithms for Greechie diagrams , volume = 39 , year = 2000, arxiv = quant-ph/0009039 {{citation , last = Munaro , first = Andrea , doi = 10.1016/j.disc.2017.01.006 , issue = 6 , journal =
Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
, 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 , doi-access = free
{{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