The Perfect Matching Hamiltonian property in Prism and Crossed Prism graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915021773078528 |
|---|---|
| author | Colangelo, Francesco Romaniello, Federico |
| author_facet | Colangelo, Francesco Romaniello, Federico |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09724 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Perfect Matching Hamiltonian property in Prism and Crossed Prism graphs Colangelo, Francesco Romaniello, Federico Combinatorics 05C15, 05C45, 05C70 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$. |
| title | The Perfect Matching Hamiltonian property in Prism and Crossed Prism graphs |
| topic | Combinatorics 05C15, 05C45, 05C70 |
| url | https://arxiv.org/abs/2411.09724 |