Vertex-pancyclism in edge-colored complete graphs with restrictions in color transitions | [Discrete Mathematics Letters • 2024]

Author(s):

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

2. 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

3. Rocio Sanchez-Lopez: Facultad de Ciencias, Universidad Nacional Auto ́noma de Me ́xico,Coyoaca ́n, CDMX, Me ́xico,

4. 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.

Page(s): 74-81

DOI: 10.47443/dml.2023.232

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

Keywords:

edgecolored graph , vertex Hpanciclicity , Hcycle , properly colored cycle

References:

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

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

[3] 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.

[4] Bondy J. A.,Baton Rouge .1971 .Pancyclic graphs. Graph Theory and Computing, : 167-172.

[5] Bondy J. A.,Pancyclic graphs I .1971 .. J. Combin. Theory Ser. B, 11 : 80-84.

[6] Bondy J. A. .1973 .Pancyclic graphs: recent results, In: Infinite and finite sets: to P. Erdo¨s on his 60th birthday. , 1 : 181-187.

[7] Bondy J. A.,Murty U. S. R. .1976 .. Graph Theory with Applications, : .

[8] Brandt S.,Faudree R. .1998 .. J. Graph Theory, 27 : 141-176.

[9] Chen X.,Huang F.,Yuan J. .2019 .Proper vertex-pancyclicity of edge-colored complete graphs without monochromatic triangles. Discrete Appl. Math, 265 : 199-203.

[10] Corneil D. G.,Perl Y.,Stewart L. K. .1985 .A linear recognition algorithm for cographs. SIAM J. Comput, 14 : 926-934.

[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.,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], : .

[15] 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.

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

[17] Hendry G. R. T. .1990 .. , 85 : 59-72.

[18] M.-C. Li D. G.,Corneil D. G. .2000 .Pancyclicity and NP-completeness in planar graphs. Discrete Appl. Math, 98 : 219-225.

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

[20] 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.

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

[22] 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.

[23] 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.

[24] 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.

[25] 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.

Citations

Downloads

Views