Content deleted Content added
→From smaller graphs: explain more |
|||
Line 18:
===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]]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.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]]
| |||