Euler dynamic H-trails in edge-colored graphs
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: se...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2024-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2023.2250837 |
| _version_ | 1797244253098737664 |
|---|---|
| author | Carlos Vilchis-Alfaro Hortensia Galeana-Sánchez |
| author_facet | Carlos Vilchis-Alfaro Hortensia Galeana-Sánchez |
| author_sort | Carlos Vilchis-Alfaro |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T02:34:29Z |
| format | Article |
| id | doaj.art-24e2d1a3d67e41d4b3c5de606f8e4a6d |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-04-24T19:08:04Z |
| publishDate | 2024-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-24e2d1a3d67e41d4b3c5de606f8e4a6d2024-03-26T14:03:25ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742024-01-01211485610.1080/09728600.2023.2250837Euler dynamic H-trails in edge-colored graphsCarlos Vilchis-Alfaro0Hortensia Galeana-Sánchez1Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la investigación científica, Circuito Exterior, Ciudad Universitaria, Coyoacán, CDMX, MéxicoInstituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la investigación científica, Circuito Exterior, Ciudad Universitaria, Coyoacán, CDMX, MéxicoAbstractAlternating 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.https://www.tandfonline.com/doi/10.1080/09728600.2023.2250837Edge colored graphdynamic H-trailEuler dynamic H-trailsHamiltonian cycles |
| spellingShingle | Carlos Vilchis-Alfaro Hortensia Galeana-Sánchez Euler dynamic H-trails in edge-colored graphs AKCE International Journal of Graphs and Combinatorics Edge colored graph dynamic H-trail Euler dynamic H-trails Hamiltonian cycles |
| title | Euler dynamic H-trails in edge-colored graphs |
| title_full | Euler dynamic H-trails in edge-colored graphs |
| title_fullStr | Euler dynamic H-trails in edge-colored graphs |
| title_full_unstemmed | Euler dynamic H-trails in edge-colored graphs |
| title_short | Euler dynamic H-trails in edge-colored graphs |
| title_sort | euler dynamic h trails in edge colored graphs |
| topic | Edge colored graph dynamic H-trail Euler dynamic H-trails Hamiltonian cycles |
| url | https://www.tandfonline.com/doi/10.1080/09728600.2023.2250837 |
| work_keys_str_mv | AT carlosvilchisalfaro eulerdynamichtrailsinedgecoloredgraphs AT hortensiagaleanasanchez eulerdynamichtrailsinedgecoloredgraphs |