Proper Hamiltonian cycles in edge-colored multigraphs

Autor: Yannis Manoussakis, Valentin Borozan, Leandro Montero, Raquel Rivera Díaz, Raquel Águeda
Přispěvatelé: University of Castilla-La Mancha (UCLM), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidad Complutense de Madrid = Complutense University of Madrid [Madrid] (UCM), Graphes, Algorithmes et Combinatoire (LRI) (GALaC - LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2017
Předmět:
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
ACM: G.: Mathematics of Computing
Theoretical Computer Science
Combinatorics
symbols.namesake
Computer Science::Discrete Mathematics
FOS: Mathematics
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
0101 mathematics
ComputingMilieux_MISCELLANEOUS
Mathematics
Discrete mathematics
Mathematics::Combinatorics
010102 general mathematics
Multigraph
Rainbow
ACM: F.: Theory of Computation
Hamiltonian path
Colored
010201 computation theory & mathematics
symbols
Combinatorics (math.CO)
Multiple edges
Hamiltonian (quantum mechanics)
Computer Science - Discrete Mathematics
Zdroj: Discrete Mathematics
Discrete Mathematics, Elsevier, 2017, 340 (8), pp.1897-1902. ⟨10.1016/j.disc.2017.03.013⟩
ISSN: 0012-365X
Popis: A $c$-edge-colored multigraph has each edge colored with one of the $c$ available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree.
Comment: 13 pages
Databáze: OpenAIRE
Externí odkaz: