Locally linear graph: Difference between revisions

Revision as of 07:26, 24 March 2025

Latest revision as of 10:33, 14 July 2025

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.jpgsvg|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. 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.