Content deleted Content added
→Constructions: rm unhelpful here |
→Constructions: move figure |
||
Line 8:
==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]]▼
===Gluing and products===
The [[friendship graph]]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.{{r|ers}} More generally every [[Cactus graph#Triangular cactus|triangular cactus graph]], a graph formed by gluing triangles at shared vertices without forming any additional cycles, is locally linear.{{r|fp}}
Line 20 ⟶ 19:
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}}
▲[[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]]
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. It follows from [[Euler's polyhedral formula]] that if <math>G</math> has <math>n</math> vertices, it has exactly <math>n-2</math> faces. 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 with <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.
| |||