Trails in arc-colored digraphs avoiding forbidden transitions | [Discrete Mathematics Letters • 2024]

Author(s):

1. Carlos Vilchis-Alfaro: Instituto de Matema ́ticas, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,

2. Hortensia Galeana-Sanchez: Instituto de Matema ́ticas, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,

Abstract:

Let H be a digraph possibly with loops. Let D be a digraph without loops. An H-coloring of D is a function c : A(D) ! V (H). We say that D is an H-colored digraph 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 every i 2 f0; : : : ; n 2g. Whenever the vertices of an H-trail are pairwise different, we say that it is an H-path. In this paper, we study the problem of finding s t H-trail in H-colored digraphs. First, we prove that finding an H-trail starting with the arc e and ending at arc f can be done in polynomial time. As a consequence, we give a polynomial time algorithm to find the shortest H-trail from a vertex s to a vertex t (if it exists). Moreover, we obtain a Menger-type theorem for H-trails. As a consequence, we show that the problem of maximizing the number of arc disjoint s t H-trails in D can be solved in polynomial time. Although finding an H-path between two given vertices is an NP-problem, it becomes a polynomial time problem in the case when H is a reflexive and transitive digraph.

Page(s): 6-12

DOI: 10.47443/dml.2023.190

Published: Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Keywords:

arccolored digraph , arccolored trails , polynomial algorithms

References:

[1] Abouelaoualim A.,K. C. Das L.,Faria Y.,Manoussakis C.,Martinhon R.,Saad R. .2008 .Paths and trails in edge-colored graphs. Theoret. Comput. Sci, 409 : 497-510.

[2] Ahuja S. K. .2010 .Algorithms for Routing and Channel Assignment in Wireless Infrastructure Networks. Ph.D. Thesis, : .

[3] Bang-Jensen J.,Bellitto T.,Yeo A. .2021 .On supereulerian 2-edge-coloured graphs. Graphs Combin, 37 : 2601-2620.

[4] Bang-Jensen J.,Gutin G. Z. .2009 .. , : .

[5] Bellitto T.,Bergougnoux B. .2018 .Graph-Theoretic Concepts in Computer Science. WG 2018, : 40-51.

[6] Bellitto T.,Li S.,Okrasa K.,Pilipczuk M.,Sorge M. .2023 .The complexity of routing problems in forbidden-transition graphs and edge-colored graphs. Algorithmica, 85 : 1202-1250.

[7] Ben G.,Bobadilla H.,Cruz H. .2024 .Panchromatic patterns by paths. Discuss. Math. Graph Theory, 44 : 519-537.

[8] Chou W.,Manoussakis Y.,Megalakaki O.,Spyratos M.,Tuza Z. .1994 .Paths through fixed vertices in edge-colored graphs. Math. Inf. Sci. Hum, 127 : 49-58.

[9] Delgado-Escalante P.,H. P. .2014 .Galeana-Sa´ nchez, Restricted domination in arc-colored digraphs. AKCE Int. J. Graphs Comb, 11 : 95-104.

[10] Delgado-Escalante P.,Galeana-Sa H.,Ram L. P. .2012 .´ırez, Independent restricted domination and the line digraph. AKCE Int. J. Graphs Comb, 9 : 31-42.

[11] Dorninger D. .1994 .Hamiltonian circuits determining the order of chromosomes, Discrete Appl. , 50 : 159-168.

[12] Dorninger D. .1987 .Geometrical constraints on Bennett's predictions of chromosome order. Heredity, 59 : 321-325.

[13] Fujita S.,Magnant C. .2011 .Properly colored paths and cycles. Discrete Appl. Math, 159 : 1391-1397.

[14] Galeana-Sa H.,Sa R.,J. I. R. .2019 .Villarreal-Valde´s, Some conditions for the existence of euler H-trails. Graphs Combin, 35 : 1197-1208.

[15] Galeana-S H.,R. H.,J. I. H. .2022 .Villarreal-Valde´s, H-cycles in H-colored multigraphs. Graphs Combin, 38 : 1-20.

[16] Galeana-S H. .2013 .a´nchez, R. S a´nchez-Lo´pez, H-kernels in infinite digraphs. Graphs Combin, 29 : 913-920.

[17] Galeana-Sa H. . .Characterizing arc-colored digraphs with an Eulerian trail with restrictions in the color transitions. , : .

[18] Gourve L.,Martinhon C. A.,Monnot J. .2013 .Complexity of trails, paths and circuits in arc-colored digraphs. Discrete Appl. Math, 161 : 819-828.

[19] Guo Z.,Broersma H.,Li B.,S. Zhang, B. .2021 .Almost eulerian compatible spanning circuits in edge-colored graphs. , 344 : 112174.

[20] Guo Z.,Li B.,Li X.,S. Zhang, X. .2020 .Compatible spanning circuits in edge-colored graphs. , 343 : 111908.

[21] Linek V.,Sands B. .1996 .A note on paths in edge-coloured tournaments. Ars Combin, 44 : 225-228.

[22] Sankararaman S.,Efrat A.,Ramasubramanian S.,Agarwal P. K. .2014 .On channel-discontinuity-constraint routing in wireless networks. Ad Hoc Netw, 13 : 153-169.

[23] Szachniuk M.,Popenda M.,Adamiak R. W.,Blazewicz J. .2009 .An assignment walk through 3D NMR spectrum. 2009 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, : 215-219.

[24] Szeider S. .2003 .Finding paths in graphs avoiding forbidden transitions. Discrete Appl. Math, 126 : 261-273.

Citations

Downloads

Views