Proper Hamiltonian Paths in Edge-Coloured Multigraphs
Preprint
Abstract
Given a $c$-edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- 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