Graph-theory open problems

Hamilton decomposition of prisms over 3-connected cubic planar graphs

OPG_prism_planar_cubic_hamilton_decomposition

Source: Open Problem Garden: decomposing_the_prism_of_a_3_connected_cubic_planar_graphs_in_hamilton_cycles

Medium ★★ Graph Theory » Basic Graph Theory » Cycles
Authors: Alspach, Brian, Rosenfeld, Moshe— posted by fhavet on 2013-03-12

Status partial high confidence

The Alspach–Rosenfeld conjecture that every prism $G\square K_2$ over a 3-connected cubic planar graph $G$ decomposes into two Hamilton cycles remains open in full generality. Significant partial results were established before the posting (bipartite planar cubic graphs, duals of kleetopes). After the 2013 posting, Rosenfeld and Xiang (2015) extended the family of confirmed cases to include prisms over cubic Halin graphs, cubic generalized Halin graphs of order $4k+2$, and several further infinite families.

Cited literature (1)

  • partial Hamiltonian decomposition of prisms over cubic graphs (2015)
    Moshe Rosenfeld, Ziqing Xiang · Discrete Mathematics and Theoretical Computer Science

    Proves the Alspach–Rosenfeld conjecture for prisms over cubic Halin graphs, cubic generalized Halin graphs of order 4k+2, and other infinite families of cubic graphs, extending the list of confirmed cases beyond what was known before 2013.

Reviewer notes. The 2004 paper by Čada, Kaiser, Rosenfeld, and Ryjáček (Discrete Math. 286, 2004) proved the conjecture for 3-connected cubic bipartite planar graphs and duals of kleetopes, but it predates the 2013 posting and is not included in since_posted. ScienceDirect and Wiley pages returned 403 Forbidden and could not be verified. No arXiv preprints were found on this exact problem. The West page (Illinois) timed out and could not be confirmed as a verified URL. The conjecture is listed as problem #85 in Bondy–Murty (2008).

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 07) (web search enabled).

Conjecture. Every prism over a $ 3 $ -connected cubic planar graph can be decomposed into two Hamilton cycles.

Discussion

The prism over a graph $ G $ is the Cartesian product $ G\square K_2 $ . Rosenfeld and Barnette [RB] deduced from the Four-Colour Theorem that the prism over cubic planar 3-connected $ G $ has a Hamilton cycle $ C $ . The graph $ G\setminus E(C) $ is cycle factor (spanning union of cycles). The conjecture says that one can choses $ C $ so that the cycle factor $ G\setminus E(C) $ has a unique cycle, that is a Hamilton cycle.

Bibliography

  • ★ [AR] B. Alspach and M. Rosenfeld, On Hamilton decompositions of prisms over simple $ 3 $ -polytopes. Graphs Combin. 2 (1986), 1--8.
  • [RB] M. Rosenfeld and D. Barnette, Hamiltonian circuits in certain prisms, Discrete Math. 5 (1973) 389–394.

Related conjectures

  • related to Barnette's conjecture on 4-regular 4-polytopes open By Steinitz, a 3-connected cubic planar graph G is the graph of a simple 3-polytope P. P x [0,1] is a simple 4-polytope, and its graph is G□K_2. So Barnette's 4-polytope conjecture, restricted to prisms, says G□K_2 is Hamiltonian. The Hamilton-decomposition conjecture also implies that statement. That shared special case is already a theorem (Rosenfeld–Barnette via 4CT, cited in the target's context). Barnette gives only one Hamilton cycle, not a decomposition. The target covers only prisms, not all simple 4-polytopes. So neither node implies the other.

View in the relation graph — relations are AI-reviewed, not formally verified.