Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs

• Published in: Discrete Applied Mathematics 2020-09, Vol.284, p.281-289
• Main Authors: Cordero-Michel, Narda, Galeana-Sánchez, Hortensia
• Format: Article
• Language: English
• Subjects: 2-edge-colored graph; Alternating cycle; Apexes; Graph coloring; Graph theory; Graphs; Vertex alternating-pancyclic graph
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2020.03.047

An alternating cycle in a 2-edge-colored graph is a cycle such that any two consecutive edges have different colors. Let G1, …, Gk be a collection of pairwise vertex disjoint 2-edge-colored graphs. The colored generalized sum of G1, …, Gk, denoted by ⊕i=1kGi, is the set of all 2-edge-colored graphs G such that: (i) V(G)=⋃i=1kV(Gi), (ii) G〈V(Gi)〉≅Gi for i=1,…,k as edge-colored graphs where G〈V(Gi)〉 has the same coloring as Gi 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=1kGi will be called a colored generalized sum (c.g.s.). A 2-edge-colored graph G of order 2n is vertex alternating-pancyclic iff, for each vertex v∈V(G) and each k∈{2,…,n}, G contains an alternating cycle of length 2k passing through v. 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=1kGi to be a vertex alternating-pancyclic graph.