Alternating-Pancyclism in 2-Edge-Colored Graphs

Cordero-Michel, Narda ; Galeana-Sánchez, Hortensia

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 779-800

Résumé

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.

Détail

Keywords: 2-edge-colored graph, alternating cycle, alternating-pancyclic graph