The Pairing-Hamiltonian property in graph prisms

Let $G$ be a graph of even order, and consider $K_G$ as the complete graph on the same vertex set as $G$. A perfect matching of $K_G$ is called a pairing of $G$. If for every pairing $M$ of $G$ it is possible to find a perfect matching $N$ of $G$ such that $M \cup N$ is a Hamiltonian cycle of $K_G$ , then $G$ is said to have the Pairing-Hamiltonian property, or $PH$-property, for short. In 2007, Fink (2007) [4] proved that for every $d \ge 2$, the $d$-dimensional hypercube $Q_d$ has the $PH$-property, thus proving a conjecture posed by Kreweras in 1996. In this paper we extend Fink’s result by proving that given a graph $G$ having the $PH$-property, the prism graph $P(G)= G \Box K_2$ of $G$ has the $PH$-property as well. Moreover, if $G$ is a connected graph, we show that there exists a positive integer $k_0$ such that the $k^{th}$-prism of a graph $P_k(G)$ has the $PH$-property for all $k \ge k_0$.