Trails in arc-colored digraphs avoiding forbidden transitions

Carlos Vilchis-Alfaro; Hortensia Galeana-Sanchez

doi:10.47443/dml.2023.190

Author(s)

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

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.

Publication Details

Page(s) 6-12

DOI 10.47443/dml.2023.190

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

Request the full text from PASTIC

Keywords

arc-colored digraph, arc-colored trails, polynomial algorithms

References

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.

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

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

Bang-Jensen J.,Gutin G. Z. .2009 .. , : .

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

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.

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

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.

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

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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.

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