No Detail Found!

Vertex-pancyclism in edge-colored complete graphs with restrictions in color transitions

Author(s)
Hortensia Galeana-Sanchez Instituto de Matema ́ticas, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,
Felipe Hernandez-Lorenzana Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, Coyoac´an, CDMX, M´exico; Facultad de Ciencias, Universidad Nacional Aut´onoma de M´exico, Coyoac´an, CDMX, M´exico
Rocio Sanchez-Lopez Facultad de Ciencias, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,
Carlos Vilchis-Alfaro Instituto de Matema ́ticas, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,
Abstract
Let H be a graph possibly with loops. Let G be a simple graph. We say that G is an H-colored graph whenever every edge of G has assigned a vertex of H as a color. A cycle C in an H-colored graph G is an H-cycle if and only if the colors of consecutive edges in C are adjacent vertices in H, including the last and first edges of C. An H-colored graph G is said to be vertex H-pancyclic if every vertex of G is contained in an H-cycle of length l for every l in f3; : : : ; jV (G)jg. A properly colored cycle in an edge-colored graph is a particular case of H-cycles in H-colored graph, namely when H is a complete graph with no loops. In this paper, we show sufficient conditions on an H-colored complete graph G to be vertex H-pancyclic. As a consequence, we obtain a well-known result about properly vertex pancyclicism in edge-colored complete graphs.
Publication Details
Page(s) 74-81
Published Journal: Discrete Mathematics Letters, Volume: 13, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords
edge-colored graph, vertex H-panciclicity, H-cycle, properly colored cycle
References
Ahuja S. K. .2010 .Algorithms for Routing and Channel Assignment in Wireless Infrastructure Networks. Ph.D. Thesis, : .
Bang-Jensen J.,Gutin G. Z. .2009 .. , : .
Benkouar A.,Manoussakis Y.,Paschos V. T.,Saad R.,Hsu R. .1991 .On the complexity of some hamiltonian and eulerian problems in edge-colored complete graphs. International Symposium on Algorithms, : 190-198.
Bondy J. A.,Baton Rouge .1971 .Pancyclic graphs. Graph Theory and Computing, : 167-172.
Bondy J. A.,Pancyclic graphs I .1971 .. J. Combin. Theory Ser. B, 11 : 80-84.
Bondy J. A. .1973 .Pancyclic graphs: recent results, In: Infinite and finite sets: to P. Erdo¨s on his 60th birthday. , 1 : 181-187.
Bondy J. A.,Murty U. S. R. .1976 .. Graph Theory with Applications, : .
Brandt S.,Faudree R. .1998 .. J. Graph Theory, 27 : 141-176.
Chen X.,Huang F.,Yuan J. .2019 .Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles. Discrete Appl. Math, 265 : 199-203.
Corneil D. G.,Perl Y.,Stewart L. K. .1985 .A linear recognition algorithm for cographs. SIAM J. Comput, 14 : 926-934.
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.,F. H.,Lorenzana R.,Sa R. .2022 .´ nchez-Lo´pez, Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in the color transitions. arXiv:2207.01699 [math.CO], : .
Galeana-S H.,Sa R.,J. I. R. .2019 .Villarreal-Valde´s, Some conditions for the existence of Euler H-trails. Graphs Comb, 35 : 1197-1208.
Galeana-Sa H.,Sa R.,J. I. R. .2022 .Villarreal-Valde´s, H-cycles in H-colored multigraphs. Graphs Combin, 38 : 1-20.
Hendry G. R. T. .1990 .. , 85 : 59-72.
M.-C. Li D. G.,Corneil D. G. .2000 .Pancyclicity and NP-completeness in planar graphs. Discrete Appl. Math, 98 : 219-225.
Linek V.,Sands B. .1996 .A note on paths in edge-coloured tournaments. Ars Combin, 44 : 225-228.
Pevzner P. A.,Tang H.,Waterman M. S. .2001 .An eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. USA, 98 : 9748-9753.
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. In: 2009 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, : 215-219.
Tseng I.-L.,C.-I. Lee I.-L.,Ao S. I.,Douglas C.,Grundfest W. S. .2010 .Obstacle-aware longest-path routing with parallel MILP solvers. Proceedings of the World Congress on Engineering and Computer Science, : 827-831.
Xu H.,Kilgour D. M.,Hipel K. W. .2010 .Using matrices to link conflict evolution and resolution in a graph model. European J. Oper. Res, 207 : 318-329.
Xu H.,Li K. W.,Kilgour D. M.,Hipel K. W. .2009 .A matrix-based approach to searching colored paths in a weighted colored multidigraph. Appl. Math. Comput, 215 : 353-366.
0

Citations

0

Downloads

42

Views