Vertex Alternating-Pancyclism in 2-Edge-Colored Graphs

Narda Cordero-Michel; Hortensia Galeana-Sánchez

paper

Vertex Alternating-Pancyclism in 2-Edge-Colored Graphs

arXiv:1910.01729

Abstract

An alternating cycle in a 2-two-edge-colored graph is a cycle such that any two consecutive edges have different colors. Let $G_{1}, \dots, G_{k}$ be a collection of pairwise vertex disjoint 2-edge-colored graphs. The colored generalized sum of $G_{1}, \dots, G_{k}$ , denoted by $\oplus_{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, \dots, k$ as edge-colored graphs 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 $\oplus_{i = 1}^{k} G_{i}$ will be called a colored generalized sum (c.g.s.) and we will say that $e \in E (G)$ is an exterior edge iff $e \in E (G) ∖ (⋃_{i = 1}^{k} E (G_{i}))$ . The set of exterior edges will be denoted by $E_{\oplus}$ . A colored graph $G$ is said to be a vertex alternating-pancyclic graph, whenever for each vertex $v$ in $G$ , and for each $l \in {3, \dots, ∣ V (G) ∣}$ , there exists in $G$ an alternating cycle of length $l$ 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 \in \oplus_{i = 1}^{k} G_{i}$ to be a vertex alternating-pancyclic graph.

14