Gregory Gutin and Bang-Jensen, J. (1998) Alternating cycles and trails in 2-edge-coloured multigraphs. Discrete Mathematics, 188 (1).
Full text access: Open
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).
This is a Published version This version's date is: 1998 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/5752c96e-e816-62ac-6a95-c31507903bdf/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 26-May-2010