2021/12/16 by R. J. Kingan, Kingan, R. J., S. R. Kingan +1 · 1 citation
Computer Science · #05C85 (Primary) 05C83 (Secondary) #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #F.2 #FOS: Mathematics #G.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2112.08825
openalex publication_date 2021/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For k ≥ 4, let Q2k and V2k denote the ladder and Möbius ladder on 2k vertices, respectively. We prove results that build on a result by Wormald that states that any cyclically 4-connected cubic graph other than Q8 or V8 is obtained from a smaller cyclically 4-connected cubic graph by bridging a pair of non-adjacent edges. We introduce the concept of cycle spread, which generalizes the edge pair distance defined by Wormald, and show that the set of pairs of edges that needs to be considered in order to obtain all cyclically 4-connected cubic graphs is smaller than the set of all pairs of non-adjacent edges. We prove that all non-planar cyclically 4-connected cubic graphs with at least 10 vertices, other than the Möbius ladders and the Petersen graph, are obtained from Q8 by bridging pairs of edges with cycle spread at least (1,2). Moreover every graph obtained in this way is non-planar, cyclically 4-connected, and cubic. All planar cyclically 4-connected cubic graphs with at least 10 vertices except for the ladders are obtained from the ladders by bridging pairs of edges with cycle spread at least (1,2). We implemented an algorithm based on these results using McKay's nauty system for isomorphism checking.