Content deleted Content added
→References: fix mangled 2nd author |
On generalized cages |
||
Line 13:
===Expansion===
If <math>G</math> is a [[cubic graph|3-regular]] [[triangle-free graph]], then the [[line graph]] <math>L(G)</math> is a graph formed by expanding each edge of <math>G</math> into a new vertex, and making two vertices adjacent in <math>L(G)</math> when the corresponding edges of <math>G</math> share an endpoint. These graphs are 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]] can be formed in this way as the line graph of a cube, and the nine-vertex [[Paley graph]] is the line graph of the [[utility graph]] <math>K_{3,3}</math>.
The line graph of the [[Petersen graph]], another graph of this type, has a property analogous to the [[Cage (graph theory)|cages]] in that 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}}
A more complicated expansion process applies to [[planar graph]]s.
Line 119 ⟶ 120:
| volume = 39
| year = 1989}}</ref>
<ref name=fan>{{citation
| last = Fan | first = Cong
| doi = 10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M
| issue = 1
| journal = Journal of Graph Theory
| mr = 1402135
| pages = 21–31
| title = On generalized cages
| volume = 23
| year = 1996}}</ref>
<ref name=lpv>{{citation
| |||