Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/118842
Title: | Extending perfect matchings to Hamiltonian cycles in line graphs |
Authors: | Abreu, Marién Gauci, John Baptist Labbate, Domenico Mazzuoccolo, Giuseppe Zerafa, Jean Paul |
Keywords: | Graph theory Graphic methods Hamiltonian graph theory Perfect numbers |
Issue Date: | 2019 |
Publisher: | Electronic Journal of Combinatorics |
Citation: | Abreu, M., Gauci, J. B., Labbate, D., Mazzuoccolo, G., & Zerafa, J. P. (2019). Extending perfect matchings to Hamiltonian cycles in line graphs. Electronic Journal of Combinatorics, 28(1), P1.7. |
Abstract: | 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. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/118842 |
Appears in Collections: | Scholarly Works - FacEduTEE |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Extending_perfect_matchings_to_Hamiltonian_cycles_in_line_graphs_2019.pdf | 312.12 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.