Extending perfect matchings to Hamiltonian cycles in line graphs
| Autor: | Abreu, Marién, Gauci, John Baptist, Labbate, Domenico, Mazzuoccolo, Giuseppe, Zerafa, Jean Paul |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Electron. J. Comb. 28, No. 1, Research Paper P1.7, 13 pgs. (2021) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.37236/9143 |
| Popis: | A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $G$ in order to guarantee that its line graph $L(G)$ has the PMH-property. In particular, we prove that this happens when $G$ is (i) a Hamiltonian graph with maximum degree at most $3$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper. Comment: 12 pages, 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|