Transformations of cubic graphs

DOI10.1016/0016-0032(96)00015-4MaRDI QIDQ1925057zbMATH OpenOpenAlexFDO

Authors Yasuyuki Tsukui

Publication date 7 April 1997

Published in Journal of the Franklin Institute (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0016-0032(96)00015-4

zbMATH Keywords

cubic graphedge-expansionedge-reductionmetrictransformations

Mathematics Subject Classification ID

Applications of graph theory (05C90)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 863637
• Transformations of edge-coloured cubic graphs
• scientific article; zbMATH DE number 1239598
• Matching transformation graphs of cubic bipartite plane graphs
• Cubic graphs with application
• ON ISOMORPHISMS OF VERTEX-TRANSITIVE CUBIC GRAPHS
• Cubical graphs and cubical dimensions
• Automorphisms of a family of cubic graphs
• On the cubicity of certain graphs
• scientific article; zbMATH DE number 4093508

Cites work

• A Proof of 4-Coloring the Edges of a Cubic Graph
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 3958250 (Why is no real title available?)
• scientific article; zbMATH DE number 3224336 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• On the Möbius Ladders
• Properties of a planar cubic graph

Cited in

(14)

• Transformations of edge-coloured cubic graphs
• Matching transformation graphs of cubic bipartite plane graphs
• A triangle process on regular graphs
• Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon
• On the complexity group of stable curves
• Transforming phylogenetic networks: moving beyond tree space
• scientific article; zbMATH DE number 4008437 (Why is no real title available?)
• scientific article; zbMATH DE number 1264876 (Why is no real title available?)
• scientific article; zbMATH DE number 863637 (Why is no real title available?)
• scientific article; zbMATH DE number 1409222 (Why is no real title available?)
• The geometry of flip graphs and mapping class groups
• On the tropical Torelli map
• Geometry of tropical moduli spaces and linkage of graphs
• Expansion properties of Whitehead moves on cubic graphs

This page was built for publication: Transformations of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1925057)