آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 113 |
| تعداد مقالات | 1,289 |
| تعداد مشاهده مقاله | 1,262,063 |
| تعداد دریافت فایل اصل مقاله | 1,115,243 |
Characterizing arc-colored digraphs with an Eulerian trail with restrictions in the color transitions | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 15 بهمن 1403 اصل مقاله (444.41 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29828.2178 | ||
| نویسندگان | ||
| Carlos Vilchis-Alfaro* ؛ Hortensia Galeana-Sánchez | ||
| Instituto de Matemáticas, Universidad Nacional Autónama de México, CDMX, México | ||
| چکیده | ||
| 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) \rightarrow V(H)$. We say that $D$ is an $H$-colored multidigraph whenever we are taking a fixed $H$-coloring of $D$. A trail $W=(v_0,e_0,v_1,e_1,v_2,\ldots,v_{n-1},e_{n-1},$ $v_n)$ in $D$ is an $H$-trail if and only if $(c(e_i),c(e_{i+1}))$ is an arc in $H$, for each $i \in \{0,\ldots,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 $f_1$ and ending with arc $f_2$, for any pair of arcs $f_1$ and $f_2$ in $D$. Let $D$ be an $H$-colored multidigraph and $u$ a vertex of $D$, the auxiliary digraph $D_u$ 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 $D_u$ is a disjoint union of complete bipartite graphs, for every $u \in V(D)$. Then $D$ has a Euler $H$-trail if and only if $D$ is $H$-trail-connected and, for every $u \in V(D)$, the underlying graph of $D_u$ 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 $D_u$ is a disjoint union of complete bipartite graphs and, possibly, isolated vertices, for every $u \in V(D)$. | ||
| کلیدواژه‌ها | ||
| Euler trails؛ Arc-colored digraphs؛ Forbidden transitions | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 21 تعداد دریافت فایل اصل مقاله: 29 |
||