Hamiltonian Cycles in Prisms (1986, 2012)

Originators: Moshe Rosenfeld    (presented by Douglas West - REGS 2012)

Definitions: The prism over a graph $G$ is the cartesian product graph $G\Box K_2$. A graph is Hamiltonian if it has a spanning cycle, and $G$ is prism-Hamiltonian if the prism over $G$ is Hamiltonian.

Background: For graphs that are prisms, typically one can weaken the conditions that suffice for various properties about spanning cycles in the absence of the restriction to prisms. For example, it is not true that all $4$-connected $4$-regular graphs are Hamiltonian. However, graphs in the subclass consisting of prisms over $3$-connected $3$-regular graphs are Hamiltonian (Paulraja [P], Rosenfeld-Barnett [RB], and [CKRR]). In general, we seek conditions on $G$ for the prism over $G$ to be Hamiltonian or to have even stronger properties about spanning cycles. The result just mentioned suggests a question.

Question 1: (Alspach-Rosenfeld [AR]) Is it true that the prism over any $3$-connected $3$-regular graph $G$ decomposes into two spanning cycles?

Comment: A positive answer is known for many classes of such graphs, including $3$-edge-colorable $3$-regular graphs in which each pair of color classes forms a spanning cycle, bipartite planar $3$-connected $3$-regular graphs [CKRR], and the Petersen graph [RB]. [AR] gives a necessary and sufficient condition for the prism over a $3$-connected $3$-regular graph to have a Hamiltonian decomposition.

It is easy to see that the prism over a Hamiltonian graph is also Hamiltonian. How much can sufficient conditions for spanning cycles be violated and still have the prism be Hamiltonian? For example, the Chvátal-Erdős Theorem [CE] states that a $k$-connected graph $G$ with independence number $a$ is Hamiltonian if $k\ge a$. Concerning regular graphs, Jackson's Theorem [J] states that a $2$-connected $k$-regular graph with at most $3k$ vertices is Hamiltonian; when $k$ is even, there are graphs with $3k+4$ vertices that are not Hamiltonian.

Question 2: (West) Given $k$, what is the largest value of $a$ such that if $G$ has connectivity $k$ and independence number $a$, then the prism over $G$ is Hamiltonian?

Comment: For $a>k$, the complete bipartite graph $K_{k,a}$ is $k$-connected and has independence number $a$. When $a>2k$, the prism over $K_{k,a}$ is not Hamiltonian, since deleting the $2k$ vertices of degree $a+1$ leaves $a$ components. Hence the answer to Question 2 is at most $2k$.

Question 3: (Rosenfeld) Given $k$, what is the largest value of $n$ such that the prism over any $2$-connected $k$-regular $n$-vertex graph is Hamiltonian?

Comments: For even $k$ with $k\ge6$, there is a $2$-connected $k$-regular graph $G$ with $5k+6$ vertices such that the prism over $G$ is not Hamiltonian.

The statement that the prism over a graph having a Hamiltonian path is Hamitonian was extended by Čada-Kaiser-Rosenfeld-Ryjáček [CKRR]. They proved that if $G$ contains a spanning subgraph that is a cactus with maximum degree at most $3$ in which all cycles have even length and all vertices of degree $3$ lie on cycles, then the prism over $G$ is Hamiltonian. They used this fact to give a short proof that the prism over a $3$-connected $3$-regular graph $G$ is Hamiltonian, starting with the fact that $G$ contains a $2$-connected spanning bipartite subgraph.

One can similarly ask how long-cycle versions of results on spanning cycles can be strengthened for prisms. The long-cycle version of Dirac's Theorem, proved by Bermond [B] and Linial [L], is that every $2$-connected $n$-vertex graph with minimum degree $d$ has a cycle of length at least $\min\{n,2d\}$.

Question 4: (West) Given $d$ and $n$, what is the largest value $c$ such that the prism over every $n$-vertex graph with minimum degree $d$ has a cycle of length at least $\min\{n,c\}$?

Comment: Many further variations are possible. For example, one can consider Ore's Condition: if the degree-sum of each pair of nonadjacent vertices is at least $d$ in a $2$-connected $n$-vertex graph $G$, what lower bound is guaranteed for the circumference of the prism over $G$? For the questions about $2$-connected graphs, one can restrict to higher connectivity. Does a slight strengthening of the conditions for a Hamiltonian prism make the prism Hamiltonian-connected? Pancyclic? Etc., etc., etc. For analogous questions about more general products than prisms, see this problem.

[AR] Alspach, Brian; Rosenfeld, Moshe; On Hamilton decompositions of prisms over simple 3-polytopes. Graphs Combin. 2 (1986), no. 1, 1-8.
[B] Bermond, J.-C.; On Hamiltonian walks. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pp. 41-51. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976.
[CKRR] Čada, Roman; Kaiser, Tomáš; Rosenfeld, Moshe; Ryjáček, Zdeněk; Hamiltonian decompositions of prisms over cubic graphs. Discrete Mathematics 286 (2004), 45-56
[CE] Chvátal, V.; Erdős, P.; A note on Hamiltonian circuits. Discrete Math. 2 (1972), 111-113.
[J] Jackson, Bill; Hamilton cycles in regular 2-connected graphs. J. Combin. Theory Ser. B 29 (1980), no. 1, 27-46.
[L] Linial, Nathan; A lower bound for the circumference of a graph. Discrete Math. 15 (1976), no. 3, 297-300.
[P] Paulraja, P.; A characterization of Hamiltonian prisms. J. Graph Theory 17 (1993), no. 2, 161-171.
[RB] Rosenfeld, Moshe; Barnette, David; Hamiltonian circuits in certain prisms. Discrete Math. 5 (1973), 389-394.