Proper Hamiltonian Cycles in Edge-Colored Multigraphs
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Proper Hamiltonian Paths in Edge-Coloured MultigraphsGraphs and Combinatorics, 2017
- Cycles and paths in edge‐colored graphs with given degreesJournal of Graph Theory, 2009
- Edge bounds in nonhamiltonian k-connected graphsDiscrete Mathematics, 2007
- Characterization of edge‐colored complete graphs with properly colored Hamilton pathsJournal of Graph Theory, 2006
- Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity resultsRAIRO - Operations Research, 1996