Geodesic
Alternating-Pancyclism in 2-Edge-Colored Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 779-800.

Voir la notice de l'article provenant de la source Library of Science

An alternating cycle in a 2-edge-colored graph is a cycle such that any two consecutive edges have different colors. Let G_1, . . ., G_k be a collection of pairwise vertex disjoint 2-edge-colored graphs. The colored generalized sum of G_1, . . ., G_k, denoted by ⊕_i=1^k G_i, is the set of all 2-edge-colored graphs G such that: (i) V(G)= ⋃ _i=1^k V(G_i), (ii) G 〈 V(G_i) 〉≅ G_i for i = 1, . . ., k where G 〈 V(G_i) 〉 has the same coloring as G_i and (iii) between each pair of vertices in different summands of G there is exactly one edge, with an arbitrary but fixed color. A graph G in ⊕_i=1^k G_i will be called a colored generalized sum (c.g.s.) and we will say that e ∈ E(G) is an exterior edge if and only if e ∈ E(G) \ ( ⋃_i=1^k E(G_i)). The set of exterior edges will be denoted by E_⊕. A 2-edge-colored graph G of order 2n is said to be an alternating-pancyclic graph, whenever for each l ∈2, . . ., n, there exists an alternating cycle of length 2l in G. The topics of pancyclism and vertex-pancyclism are deeply and widely studied by several authors. The existence of alternating cycles in 2-edge-colored graphs has been studied because of its many applications. In this paper, we give sufficient conditions for a graph G ∈⊕_i=1^k G_i to be an alternating-pancyclic graph.
Keywords: 2-edge-colored graph, alternating cycle, alternating-pancyclic graph 
@article{DMGT_2021_41_3_a5,
     author = {Cordero-Michel, Narda and Galeana-S\'anchez, Hortensia},
     title = {Alternating-Pancyclism in {2-Edge-Colored} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {779--800},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a5/}
}
TY  - JOUR
AU  - Cordero-Michel, Narda
AU  - Galeana-Sánchez, Hortensia
TI  - Alternating-Pancyclism in 2-Edge-Colored Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 779
EP  - 800
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a5/
LA  - en
ID  - DMGT_2021_41_3_a5
ER  - 
%0 Journal Article
%A Cordero-Michel, Narda
%A Galeana-Sánchez, Hortensia
%T Alternating-Pancyclism in 2-Edge-Colored Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 779-800
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a5/
%G en
%F DMGT_2021_41_3_a5
Cordero-Michel, Narda; Galeana-Sánchez, Hortensia. Alternating-Pancyclism in 2-Edge-Colored Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 779-800. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a5/

[1] J. Bang-Jensen and G. Gutin, Alternating cycles and paths in edge-coloured multi-graphs: A survey, Discrete Math. 165/166 (1997) 39–60. doi:10.1016/S0012-365X(96)00160-4

[2] J. Bang-Jensen and G. Gutin, Alternating cycles and trails in 2 -edge-coloured complete multigraphs, Discrete Math. 188 (1998) 61–72. doi:10.1016/S0012-365X(97)00274-4

[3] J. Bang-Jensen and G.Z. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag London, Ltd, London, 2009). doi:10.1007/978-1-84800-998-1

[4] W.S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos and Zs. Tuza, Paths through fixed vertices in edge-colored graphs, Math. Sci. Hum. 127 (1994) 49–58.

[5] A. Contreras-Balbuena, H. Galeana-Sánchez and I.A. Goldfeder, A new sufficient condition for the existence of alternating Hamiltonian cycles in 2 -edge-colored multi-graphs, Discrete Appl. Math. 229 (2017) 55–63. doi:10.1016/j.dam.2017.04.033

[6] N. Cordero-Michel and H. Galeana-Sánchez, Vertex alternating-pancyclism in 2- edge-colored generalized sum of graphs, Discrete Appl. Math 284 (2020) 281–289. doi:10.1016/j.dam.2020.03.047

[7] P. Das, Pan-alternating cyclic edge-partitioned graphs, Ars Combin. 14 (1982) 105–114.

[8] D. Dorninger, On permutations of chromosomes, in: Contributions to General Algebra 5, Proceedings of the Salzburg Conference, May 29-June 1, 1986, Hölder-Pichler-Tempsky (Ed(s)), (Teubner-Verlag, Stuttgart, 1987) 95–103.

[9] D. Dorninger, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math. 50 (1994) 159–168. doi:10.1016/0166-218X(92)00171-H

[10] D. Dorninger and W. Timischl, Geometrical constraints on Bennett’s predictions of chromosome order, Heredity 59 (1987) 321–325. doi:10.1038/hdy.1987.138

[11] S. Fujita and C. Magnant, Properly colored paths and cycles, Discrete Appl. Math. 159 (2011) 1391–1397. doi:10.1016/j.dam.2011.06.005

[12] A. Gorbenko and V. Popov, The Hamiltonian alternating path problem, IAENG Int. J. Appl. Math. 42 (2012) 204–213.

[13] L. Gourves, A. Lyra, C. Martinhon and J. Monnot, The minimum reload s – t path, trail and walk problems, Discrete Appl. Math. 158 (2010) 1404–1417. doi:10.1016/j.dam.2010.03.009

[14] R. Häggkvist and Y. Manoussakis, Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica 9 (1989) 33–38. doi:10.1007/BF02122681

[15] J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220. doi:10.1007/BF02392606

[16] P.A. Pevzner, DNA physical mapping and alternating Eulerian cycles in colored graphs, Algorithmica 13 (1995) 77–105. doi:10.1007/BF01188582

[17] G. Wang and H. Li, Color degree and alternating cycles in edge-colored graphs, Discrete Math. 309 (2009) 4349–4354. doi:10.1016/j.disc.2009.01.016

[18] H.C. Wirth and J. Ste an, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73–85. doi:10.1016/S0166-218X(00)00392-9

[19] 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) 318–329. doi:10.1016/j.ejor.2010.03.025

[20] H. Xu, K.W. Li, K.W. Hipel and D.M. Kilgour, A matrix approach to status quo analysis in the graph model for conflict resolution, Appl. Math. Comput. 212 (2009) 470–480. doi:10.1016/j.amc.2009.02.051

[21] 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) 353–366. doi:10.1016/j.amc.2009.04.086