Proper Hamiltonian cycles in edge-colored multigraphs

DOI10.1016/J.DISC.2017.03.013MaRDI QIDQ2397532zbMATH OpenOpenAlexFDO

Authors R. Águeda, V. Borozan, Raquel Díaz, Y. Manoussakis, Leandro Montero

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.5240, https://eprints.ucm.es/43762/1/DiazRaquel10%20libre.pdf

zbMATH Keywords

multigraphedge-colored graphproper Hamiltonian cycle

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15)

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.

Recommendations

• Cycles and paths in edge‐colored graphs with given degrees
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Multicolored parallelisms of Hamiltonian cycles

Cites work

• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 3257168 (Why is no real title available?)
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Characterization of edge-colored complete graphs with properly colored Hamilton paths
• Cycles and paths in edge‐colored graphs with given degrees
• Edge bounds in nonhamiltonian k-connected graphs
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results

Cited in

(5)

• \(H\)-cycles in \(H\)-colored multigraphs
• On Rainbow Cycles and Proper Edge Colorings of Generalized Polygons
• Multicolored parallelisms of Hamiltonian cycles
• Dynamic cycles in edge-colored multigraphs
• Properly coloured Hamiltonian paths in edge-coloured complete graphs

This page was built for publication: Proper Hamiltonian cycles in edge-colored multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397532)