Alternating Hamiltonian cycles in 2-edge-colored multigraphs

zbMATH Open1417.05061arXiv1810.04372MaRDI QIDQ5226832FDOQ5226832

Authors: Alejandro Contreras-Balbuena, Hortensia Galeana-Sánchez, Ilan A. Goldfeder 

Publication date: 1 August 2019

Abstract: A path (cycle) in a $2$-edge-colored multigraph is alternating if no two consecutive edges have the same color. The problem of determining the existence of alternating Hamiltonian paths and cycles in $2$-edge-colored multigraphs is an $mathcalNP$-complete problem and it has been studied by several authors. In Bang-Jensen and Gutin's book "Digraphs: Theory, Algorithms and Applications", it is devoted one chapter to survey the last results on this topic. Most results on the existence of alternating Hamiltonian paths and cycles concern on complete and bipartite complete multigraphs and a few ones on multigraphs with high monochromatic degrees or regular monochromatic subgraphs. In this work, we use a different approach imposing local conditions on the multigraphs and it is worthwhile to notice that the class of multigraphs we deal with is much larger than, and includes, complete multigraphs, and we provide a full characterization of this class. Given a $2$-edge-colored multigraph $G$, we say that $G$ is $2$-$mathcalM$-closed (resp. $2$-$mathcalNM$-closed)} if for every monochromatic (resp. non-monochromatic) $2$-path $P=(x_1,x_2,x_3)$, there exists an edge between $x_1$ and $x_3$. In this work we provide the following characterization: A $2$-$mathcalM$-closed multigraph has an alternating Hamiltonian cycle if and only if it is color-connected and it has an alternating cycle factor. Furthermore, we construct an infinite family of $2$-$mathcalNM$-closed graphs, color-connected, with an alternating cycle factor, and with no alternating Hamiltonian cycle.

Full work available at URL: https://arxiv.org/abs/1810.04372

Recommendations

• A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Alternating cycles in edge-colored graphs

zbMATH Keywords

Hamiltonian cyclesalternating Hamiltonian cyclesedge-colored multigraphs

Mathematics Subject Classification ID

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

Cited In (5)

• On connectivities of edge-colored graphs
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Title not available (Why is that?)
• On supereulerian 2-edge-coloured graphs
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs

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

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