Content deleted Content added
| (4 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Graph where every edge is in one triangle}}
[[File:
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 [[neighborhood (graph theory)|neighbors]] are each adjacent to exactly one other neighbor. That is,
Many constructions for locally linear graphs are known. Examples of locally linear graphs include the [[triangular cactus graph]]s, the [[line graph]]s of 3-regular [[triangle-free graph]]s, and the [[Cartesian product of graphs|Cartesian products]] of smaller locally linear graphs. Certain [[Kneser graph]]s, and certain [[strongly regular graph]]s, are also locally linear.
Line 20:
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. It has a triangle for every vertex <math>v</math> of <math>G</math>, with the vertices of the triangle corresponding to the three edges incident to <math>v</math>. 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}}
[[File:Cuboctahedron.
A more complicated expansion process applies to [[planar graph]]s. Let <math>G</math> 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 <math>G</math>, and then deleting the original edges of <math>G</math>, 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 <math>G</math> has <math>n</math> vertices, it has exactly <math>n-2</math> faces, and the result of replacing the faces of <math>G</math> by antiprisms has <math>5(n-2)+2</math> vertices and <math>12(n-2)</math> edges.{{r|z}} 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.
Line 81:
| title = Structure and uniqueness of the (81,20,1,6) strongly regular graph
| volume = 106/107
| year = 1992| doi-access =
}}</ref>
Line 258:
| title = Algorithms for Greechie diagrams
| volume = 39
| year = 2000
}}</ref>
<ref name=mun>{{citation
| |||