Perfect matchings and Hamiltonicity in the Cartesian product of cycles
| Autor: | Gauci, John Baptist, Zerafa, Jean Paul |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Ann. Comb. 25, No. 3, 789-796 (2021). SharedIt link: https://rdcu.be/csdJK |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00026-021-00548-1 |
| Popis: | A pairing of a graph $G$ is a perfect matching of the complete graph having the same vertex set as $G$. If every pairing of $G$ can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from $G$, then $G$ has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of $G$ can be extended to a Hamiltonian cycle of $G$. In an attempt to characterise all 4-regular graphs having the PH-property, we answer a question made in 2015 by Alahmadi et al. by showing that the Cartesian product $C_p\square C_q$ of two cycles on $p$ and $q$ vertices does not have the PMH-property, except for $C_4\square C_4$ which is known to have the PH-property. Comment: 6 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|