Characterizing arc-colored digraphs with an Eulerian trail with restrictions in the color transitions

Articles in Press

Document Type : Original paper

Authors

Instituto de Matemáticas, Universidad Nacional Autónama de México, CDMX, México

Abstract

Let H be a digraph possibly with loops, and D a multidigraph without loops. An H-coloring of D is a function c:A(D)→V(H). We say that D is an H-colored multidigraph whenever we are taking a fixed H-coloring of D. A trail W=(v0,e0,v1,e1,v2,…,vn−1,en−1, vn) in D is an H-trail if and only if (c(ei),c(ei+1)) is an arc in H, for each i∈{0,…,n−2}. We say that an H-colored multidigraph is H-trail-connected if and only if there is an H-trail starting with arc f1 and ending with arc f2, for any pair of arcs f1 and f2 in D. Let D be an H-colored multidigraph and u a vertex of D, the auxiliary digraph Du is the digraph of allowed transition throughout u.



In this paper we give the following characterization: Let D be an H-colored multidigraph such that the underlying graph of Du is a disjoint union of complete bipartite graphs, for every u∈V(D). Then D has a Euler H-trail if and only if D is H-trail-connected and, for every u∈V(D), the underlying graph of Du has a perfect matching. As a consequence we obtain the well-known characterization of the 2-arc-colored multidigraphs containing properly colored Euler trail. Finally, we give an infinite family of digraphs H such that for every multidigraph D without isolated vertices, and every H-coloring of D, the underlying graph of Du is a disjoint union of complete bipartite graphs and, possibly, isolated vertices, for every u∈V(D).

Keywords

Main Subjects

References

[1] S.K. Ahuja, Algorithms for Routing and Channel Assignment in Wireless Infrastructure Networks, The University of Arizona, 2010.
[2] J. Bang-Jensen, T. Bellitto, and A. Yeo, On supereulerian 2-edge-coloured graphs, Graphs Combin. 37 (2021), no. 6, 2601–2620.  https://doi.org/10.1007/s00373-021-02377-8
[3] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, 2008.
[4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan London, 1976.
[5] J.M. Carraher and S.G. Hartke, Eulerian circuits with no monochromatic transitions in edge-colored digraphs, SIAM J. Discrete Math. 27 (2013), no. 4, 1924–1939.  https://doi.org/10.1137/120878732
[6]  J.M. Carraher and S.G. Hartke, Eulerian circuits with no monochromatic transitions in edge-colored digraphs with all vertices of outdegree three, SIAM J. Discrete Math. 31 (2017), no. 1, 190–209. https://doi.org/10.1137/140992850
[7] D. Dorninger, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math. 50 (1994), no. 2, 159–168.  https://doi.org/10.1016/0166-218X(92)00171-H
[8] D. Dorninger and W. Timischl, Geometrical constraints on bennett’s predictions of chromosome order, Heredity 59 (1987), no. 3, 321–325.  https://doi.org/10.1038/hdy.1987.138
[9] H. Galeana-Sánchez, R. Rojas-Monroy, R. Sánchez-López, and J.I. Villarreal-Valdés, Some conditions for the existence of euler h-trails, Graphs Combin. 35 (2019), no. 5, 1197–1208.  https://doi.org/10.1007/s00373-019-02066-7
[10] L. Gourvés, A. Lyra, C.A. Martinhon, and J. Monnot, Complexity of trails, paths and circuits in arc-colored digraphs, Discrete Appl. Math. 161 (2013), no. 6, 819–828.  https://doi.org/10.1016/j.dam.2012.10.025
[11] G. Gutin, B. Sudakov, and A. Yeo, Note on alternating directed cycles, Discrete Math. 191 (1998), no. 1-3, 101–107. https://doi.org/10.1016/S0012-365X(98)00097-1
[12] F. Harary and C.S.J. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965), no. 6, 701–709. https://doi.org/10.4153/CMB-1965-051-3
[13] M. Imori, M. Matsumoto, and H. Yamada, The line digraph of a regular and pancircular digraph is also regular and pancircular, Graphs Combin. 4 (1988), no. 1, 235–239.  https://doi.org/10.1007/BF01864164
[14] P.W. Kasteleyn, A soluble self-avoiding walk problem, Physica 29 (1963), no. 12, 1329–1337. https://doi.org/10.1016/S0031-8914(63)80241-4
[15] A. Kotzig, Moves without forbidden transitions in a graph, Matematický časopis 18 (1968), no. 1, 76–80.
[16] V. Linek and B. Sands, A note on paths in edge-coloured tournaments, Ars Combin. 44 (1996), 225–228.
[17] P.A. Pevzner, Dna physical mapping and alternating eulerian cycles in colored graphs, Algorithmica 13 (1995), no. 1, 77–105.  https://doi.org/10.1007/BF01188582
[18] P.A. Pevzner, H. Tang, and M.S. Waterman, An eulerian path approach to dna fragment assembly, Proc. Nat. Acad. Sci. 98 (2001), no. 17, 9748–9753.  https://doi.org/10.1073/pnas.171285098
[19] S. Sankararaman, A. Efrat, S. Ramasubramanian, and P.K. Agarwal, On channel-discontinuity-constraint routing in wireless networks, Ad Hoc Netw. 13 (2014), 153–169.  https://doi.org/10.1016/j.adhoc.2011.04.011
[20] B. Sheng, R. Li, and G. Gutin, The euler and chinese postman problems on 2-arc-colored digraphs, arXiv preprint arXiv:1707.06503 (2017).
[21] H. Xu, D.M. Kilgour, K.W. Hipel, and G. Kemkes, Using matrices to link conflict evolution and resolution in a graph model, European J. Oper. Res. 207 (2010), no. 1, 318–329. https://doi.org/10.1016/j.ejor.2010.03.025
[22] H. Xu, K.W. Li, D.M. Kilgour, and K.W. Hipel, A matrix-based approach to searching colored paths in a weighted colored multidigraph, Appl. Math. Comput. 215 (2009), no. 1, 353–366. https://doi.org/10.1016/j.amc.2009.04.086
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 03 February 2025

Files

Share

How to cite

Statistics