Euler dynamic H -trails in edge-colored graphs

• Published in: AKCE international journal of graphs and combinatorics 2024-01, Vol.21 (1), p.48-56
• Main Authors: Vilchis-Alfaro, Carlos, Galeana-Sánchez, Hortensia
• Format: Article
• Language: English
• Subjects: dynamic H-trail; Edge colored graph; Euler dynamic H-trails; Hamiltonian cycles
• ISSN: 0972-8600; 2543-3474
• DOI: 10.1080/09728600.2023.2250837

AbstractAlternating 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 [Formula: see text] in G, where for each [Formula: see text] and [Formula: see text] is an edge in G, for every [Formula: see text], is a dynamic H-trail if W does not repeat edges and [Formula: see text] is an edge in H, for each [Formula: see text]. In particular, a dynamic H-trail is an alternating trail when H is a complete graph without loops and ki = 1, for every [Formula: see text]. 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, [Formula: see text], in a closed dynamic H-trail in G, and vice versa, where [Formula: see text] is a non-colored simple graph obtained from G in a polynomial time.