Content deleted Content added
→Density: ce |
change section hierarchy — regularity does not really fit into constructions |
||
Line 6:
The question of how dense 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]]. Some locally linear graphs have a number of edges that is within a small, but non-constant, factor of the number of vertex pairs. The densest [[planar graph]]s that can be locally linear are also known.
==Constructions
[[File:Cuboctahedron.jpg|thumb|The [[cuboctahedron]], a planar locally linear graph that can be formed as the line graph of a cube or by gluing antiprisms onto the inside and outside faces of a 4-cycle]]
Several constructions for locally linear graphs are known.
Line 18:
The [[Cartesian product of graphs|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.{{r|f}} The [[Hamming graph]] <math>H(d,3)</math> is a Cartesian product of <math>d</math> triangles, and again is locally linear.{{r|djlp}}
===
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]]s. For any graph <math>G</math>, the line graph <math>L(G)</math> is a graph that has a vertex for every edge of <math>G</math>. Two vertices in <math>L(G)</math> are adjacent when the two edges that they represent in <math>G</math> have a common endpoint. If <math>G</math> is a [[cubic graph|3-regular]] [[triangle-free graph]], then its line graph <math>L(G)</math> is 4-regular and locally linear. Every 4-regular locally linear graph can be constructed in this way.{{r|mun}} 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]] <math>K_{3,3}</math>. The line graph of the [[Petersen graph]] is also locally linear by this construction. It has a property analogous to the [[Cage (graph theory)|cages]]: it is the smallest possible graph in which the largest [[Clique (graph theory)|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.{{r|fan}}
Line 29:
Let <math>p</math> be a prime number, and let <math>A</math> be a subset of the numbers modulo <math>p</math> such that no three members of <math>A</math> form an [[arithmetic progression]] modulo <math>p</math>. (That is, <math>A</math> is a [[Salem–Spencer set]] modulo <math>p</math>.) This set can be used to construct a [[tripartite graph]] with <math>3p</math> vertices and <math>3|A|p</math> edges that is locally linear. To construct this graph, make three sets of vertices, each numbered from <math>0</math> to <math>p-1</math>, and construct triangles using one vertex from each of the three sets that connect vertices numbered <math>(x,x+a,x+2a)</math> modulo <math>p</math>, where <math>x</math> is any number in the range from <math>0</math> to <math>p-1</math> and <math>a</math> is any element of <math>A</math>. By construction, every edge of the resulting graph belongs to a triangle, but there can be no other triangles than the ones formed in this way. Any other triangle would have vertices numbered <math>(x,x+a,x+a+b)</math> where <math>a</math>, <math>b</math>, and <math>c=(a+b)/2</math> all belong to <math>A</math>, violating the assumption that there be no arithmetic progressions <math>(a,c,b)</math> in <math>A</math>.{{r|rs}} For example, with <math>p=3</math> and <math>A=\{\pm 1\}</math>, the result of this construction is the nine-vertex Paley graph.
==Regularity==
===Regular and strongly regular graphs===▼
===Regular graphs with few vertices===
Every locally linear graph must have even [[degree (graph theory)|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.{{r|f}}
The <math>2r</math>-regular locally linear graphs must have at least <math>6r-3</math> 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 <math>r</math> 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 <math>K_3</math>, the 9-vertex 4-regular Paley graph, the 15-vertex 6-regular Kneser graph <math>KG_{6,2}</math>, 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]].{{r|lpv}}
A [[strongly regular graph]] can be characterized by a quadruple of parameters <math>(n,k,\lambda,\mu)</math> where <math>n</math> is the number of vertices, <math>k</math> is the number of incident edges per vertex, <math>\lambda</math> is the number of shared neighbors for every adjacent pair of vertices, and <math>\mu</math> is the number of shared neighbors for every non-adjacent pair of vertices. When <math>\lambda=1</math> the graph is locally linear. The locally linear graphs already mentioned above that are strongly regular graphs and their parameters are{{r|mak}}
*the triangle (3,2,1,0),
Line 45 ⟶ 48:
Other potentially-valid combinations with <math>\lambda=1</math> include (99,14,1,2) and (115,18,1,3) but it is unknown whether strongly regular graphs with those parameters exist.{{r|mak}} 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.{{r|zd}}
===Distance=regular graphs===
There are finitely many [[distance-regular graph]]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 <math>H(3,3)</math>, and the [[Bipartite half|halved]] [[Foster graph]].{{r|hns}}
| |||