Transformations of cubic graphs (Q1925057)

For a cubic graph, an edge-reduction, edge-expansion and three transformations (S-, X-, and H-transformations) are defined which preserve regularity. Some relations between them are discussed and it is proved that for any two connected cubic graphs with the same order one can be obtained from the other by a finite sequence of S-transformations. This implies that if for any two connected cubic graphs \(G\) and \(H\), \(d(G,H)\) denotes the minimum number of edge-reductions and/or edge-expansions from \(G\) to \(H\), then \(d\) defines a metric on the set of all connected cubic graphs.