The Perfect Matching Hamiltonian property in Prism and Crossed Prism graphs
| Autor: | Colangelo, Francesco, Romaniello, Federico |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $Cube\ graph$, and indicate for which values of $n$ the \emph{Crossed Prism graphs} $\cCP_n$ are $PMH$. Comment: 19 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:2106.00513 |
| Databáze: | arXiv |
| Externí odkaz: |
|