Alternating-Pancyclism in 2-Edge-Colored Graphs

Abstract

An alternating cycle in a 2-edge-colored graph is a cycle such that any two consecutive edges have different colors. Let G1, . . ., Gkbe a collection of pairwise vertex disjoint 2-edge-colored graphs. The colored generalized sum of G1, . . ., Gk, denoted by ⊕i=1kGi \oplus _{i = 1}^k{G_i}, is the set of all 2-edge-colored graphs G such that: (i) V(G)=∪i=1kV(Gi)V\left( G \right) = \bigcup\nolimits_{i = 1}^k {V\left( {{G_i}} \right)}, (ii) G〈V (Gi) 〉 ≅ Gi for i = 1, . . ., k 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=1kGiG\,in\, \oplus _{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=1kE(Gi))e \in E\left( G \right)\backslash \left( {\bigcup\nolimits_{i = 1}^k {E\left( {{G_i}} \right)} } \right). 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.

Keywords

• 2-edge-colored graph
• alternating cycle
• alternating-pancyclic graph
• 05c38