The Pairing-Hamiltonian property in graph prisms

Abstract

Let G be a graph of even order, and consider KG as the complete graph on the same vertex set as G. A perfect matching of KG 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 ∪ N is a Hamiltonian cycle of KG, then G is said to have the Pairing-Hamiltonian property, or PH-property, for short. In 2007, Fink [J. Combin. Theory Ser. B, 97] proved that for every d ≥ 2, the d-dimensional hypercube Qd 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□K2 of G has the PH-property as well. Moreover, if G is a connected graph, we show that there exists a positive integer k0 such that the k th-prism of a graph P k (G) has the PH-property for all k ≥ k0.