Euler dynamic H -trails in edge-colored graphs
Carlos Vilchis-Alfaro, Hortensia Galeana‐Sánchez · AKCE International Journal of Graphs and Combinatorics · 2023
Alternating Euler trails has been extensively studied for its diverse practical and theoretical applications. Let H be a graph possibly with loops and G be a multigraph without loops. In this paper we deal with any fixed coloration of E(G) with V(H) (H-coloring of G). A sequence W=(v0,e01,…,e0k0,v1,e11,…,en−1kn−1,vn) in G, where for each i∈{0,…,n−1},ki≥1 and eij=vivi+1 is an edge in G, for every j∈{1,…,ki}, is a dynamic H-trail if W does not repeat edges and c(eiki)c(ei+11) is an edge in H, for each i∈{0,…,n−2}. In particular, a dynamic H-trail is an alternating trail when H is a complete graph without loops and ki = 1, for every i∈{1,…,n−1}. In this paper, we introduce the concept of dynamic H-trail, which arises in a natural way in the modeling of many practical problems, in particular, in theoretical computer science.We provide necessary and sufficient conditions for the existence of closed Euler dynamic H-trail in H-colored multigraphs. Also we provide polynomial time algorithms that allows us to convert a cycle in an auxiliary graph, L2H(G), in a closed dynamic H-trail in G, and vice versa, where L2H(G) is a non-colored simple graph obtained from G in a polynomial time.