×

A new sufficient condition for the existence of alternating Hamiltonian cycles in 2-edge-colored multigraphs. (English) Zbl 1367.05121

Summary: A path (cycle) in a \(c\)-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 NP-complete and it has been studied by several authors. Given a \(2\)-colored multigraph \(G\), an alternating \(3\)-path \(P = (x_1, x_2, x_3, x_4)\) is closed-alternating if there exist \(y\), \(w \in V(G)\) such that \(C = (x_1, y, w, x_4, x_1)\) is an alternating cycle. Furthermore, \(G\) is closed-alternating whenever each alternating \(3\)-path is closed-alternating. In this work, we prove that if \(G\) is connected, closed-alternating and it has an alternating cycle factor (i.e., a collection of vertex-disjoint alternating cycles that covers all the vertices), then \(G\) has an alternating Hamiltonian cycle.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abouelaoualim, A.; Das, K. Ch.; Faria, L.; Manoussakis, Y.; Martinhon, C.; Saad, R., Paths and trails in edge-colored graphs, Theor. Comput. Sci., 409, 497-510 (2008) · Zbl 1155.68053
[2] Abouelaoualim, A.; Das, K. Ch.; Fernandez de la Vega, W.; Karpinski, M.; Manoussakis, Y.; Martinhon, C. A.; Saad, R., Cycles and paths in edge colored graphs with given degrees, J. Graph Theory, 64, 1, 63-86 (2010) · Zbl 1202.05067
[3] Bang-Jensen, J.; Gutin, G., Alternating cycles and paths in edge-coloured multigraphs: a survey, Discrete Math., 16, 5-166 (1997), 39-60; Graphs and combinatorics (Marseille, 1995) · Zbl 0876.05057
[4] Bang-Jensen, J.; Gutin, G., (Digraphs. Theory, Algorithms and Applications. Digraphs. Theory, Algorithms and Applications, Springer Monographs in Mathematics (2009), Springer-Verlag London, Ltd: Springer-Verlag London, Ltd London), pp. xxii+795 · Zbl 1170.05002
[6] Chou, W. S.; Manoussakis, Y.; Megalakaki, O.; Spyratos, M.; Tuza, Zs., Paths through fixed vertices in edge-colored graphs, Math. Inform. Sci. Hum., 127, 49-58 (1994) · Zbl 0826.68064
[8] Dorninger, D., Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math., 50, 2, 159-168 (1994) · Zbl 0823.92010
[9] Dorninger, D.; Timischl, W., Geometrical constraints on Bennet’s predictions of chromosome order, Heredity, 58, 321-325 (1987)
[10] Feng, J.; Giesen, H.-E.; Guo, Y.; Gutin, G.; Jensen, T.; Rafiey, A., Characterization of edge-colored complete graphs with properly colored Hamilton paths, J. Graph Theory, 53, 4, 333-346 (2006) · Zbl 1125.05037
[11] Gorbenko, A.; Popov, V., The Hamiltonian alternating path problem, IAENG Int. J. Appl. Math., 42, 4, 204-213 (2012) · Zbl 1512.68309
[12] Gourvès, L.; Lyra, A.; Martinhon, C.; Monnot, J., The minimum reload \(s-t\) path, trail and walk problems, Discrete Appl. Math., 158, 13, 1404-1417 (2010) · Zbl 1209.05131
[13] Gutin, G.; Jones, M.; Sheng, B.; Wahlström, M.; Yeo, A., Chinese postman problem on edge-colored multigraphs, Discrete Appl. Math. (2016) · Zbl 1358.05105
[14] Gutin, G.; Jones, M.; Sheng, B.; Wahlström, M.; Yeo, A., Acyclicity in edge-colored graphs, Discrete Math., 340, 1-8 (2017) · Zbl 1351.05075
[15] Hilton, A. J.W., Alternating Hamiltonian circuits in edge-coloured bipartite graphs, Discrete Appl. Math., 35, 3, 271-273 (1992) · Zbl 0751.05066
[16] Kano, M.; Li, X., Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey, Graphs Combin., 24, 4, 237-263 (2008) · Zbl 1190.05045
[17] Li, X.; Magnant, C., Properly colored notions of connectivity—a dynamic survey, Theory Appl. Graphs, 0, 1, art. 2 (2015)
[18] Lo, A., An edge-colored version of Dirac’s theorem, SIAM J. Discrete Math., 28, 1, 18-36 (2014) · Zbl 1297.05085
[19] Lo, A., A dirac type condition for properly coloured paths and cycles, J. Graph Theory, 76, 1, 60-87 (2014) · Zbl 1294.05077
[20] Lo, A., Properly coloured Hamiltonian cycles in edge-coloured complete graphs, Combinatorica, 36, 4, 471-492 (2016) · Zbl 1389.05043
[21] Petersen, J., Die Theorie der regulären graphs, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03
[22] Pevzner, P. A., Dna physical mapping and properly edge-colored eulerian cycles in colored graphs, Algorithmica, 13, 77-105 (1995) · Zbl 0840.92011
[23] Saad, R., Finding a longest alternating cycle in a \(2\)-edge-coloured complete graph is in RP, Combin. Probab. Comput., 5, 3, 297-306 (1996) · Zbl 0865.05054
[24] Wirth, H. C.; Steffan, J., Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math., 113, 73-85 (2001) · Zbl 1003.05061
[25] Xu, H.; Kilgour, D. M.; Hipel, K. W.; Kemkes, G., Using matrices to link conflict evolution and resolution in a graph model, European J. Oper. Res., 207, 1, 318-329 (2010) · Zbl 1205.05233
[26] Xu, H.; Li, K. W.; Hipel, K. W.; Kilgour, D. M., A matrix approach to status quo analysis in the graph model for conflict resolution, Appl. Math. Comput., 212, 2, 470-480 (2009) · Zbl 1220.68088
[27] Xu, H.; Li, K. W.; Kilgour, D. M.; Hipel, K. W., A matrix-based approach to searching colored paths in a weighted colored multidigraph, Appl. Math. Comput., 215, 1, 353-366 (2009) · Zbl 1175.05066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.