The Pairing-Hamiltonian property in graph prisms

Abstract: 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 c u p 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 [J. Combin. Theory Ser. B, 97] proved that for every

d g e q 2

, the

d

-dimensional hypercube

m a t h c a l 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

m a t h c a l P (G)

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^{e x t r m t h}

-prism of a graph

m a t h c a l P^{k} (G)

has the PH-property for all

k g e k_{0}

.

This page was built for publication: The Pairing-Hamiltonian property in graph prisms