The Perfect Matching Hamiltonian property in Prism and Crossed Prism graphs

Abstract

A graph $G$ has the \emph{Perfect Matching Hamiltonian property} (or for short, $G$ is $PMH$) if, for each one of its perfect matchings, there is another perfect matching of $G$ such that the union of the two perfect matchings yields a Hamiltonian cycle of $G$. In this note, we show that \emph{Prism graphs} $\cP_n$ are not $PMH$, except for the $Cubegraph$, and indicate for which values of $n$ the \emph{Crossed Prism graphs} $\cCP_n$ are $PMH$.

19 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:2106.00513