Alternating cycles and trails in 2-edge-coloured multigraphs

Abstract

We consider edge-coloured multigraphs. A trail in such a multigraph is alternating if its successive edges differ in colour. Let G be a 2-edge-coloured complete graph and let M be a 2-edge-coloured complete multigraph. Bankfalvi and Bankfalvi (1968) obtained a necessary and sufficient condition for G to have a Hamiltonian alternating cycle. Generalizing this theorem, Das and Rao (1983) characterized those G which contain a closed alternating trail visiting each vertex v in G exactly f(v) > 0 times. We solve the more general problem of determining the length of a longest closed alternating trail Tf visiting each vertex v in M at most f(v) > 0 times. Our result is a generalization of a theorem by Saad (1996) that determines the length of a longest alternating cycle in G. We prove the existence of a polynomial algorithm for finding the desired trail Tf. In particular, this provides a solution to a question in Saad (1996).