Euler dynamic H-trails in edge-colored graphs

arXiv2207.03623MaRDI QIDQ6404348FDOQ6404348

Authors: Hortensia Galeana-Sánchez, Carlos Vilchis-Alfaro 

Publication date: 7 July 2022

Abstract: Alternating Euler trails has been extensively studied for its diverse applications, for example, in genetic and molecular biology, social science and channel assignment in wireless networks, as well as for theoretical reasons. We will consider the following edge-coloring. Let $H$ be a graph possibly with loops and $G$ a graph without loops. An $H$-coloring of $G$ is a function $c:E(G)ightarrowV(H)$. We will say that $G$ is an $H$-colored graph whenever we are taking a fixed $H$-coloring of $G$. A sequence $W=(v_0,e_0^1,ldots,e_0^{k_0},v_1,e_1^1,ldots,e_{n-1}^{k_{n-1}},v_n)$ in $G$, where for each $iin0,ldots,n-1$, $k_{i}geq1$ and $e_i^j=v_i{v}_{i+1}$ is an edge in $G$, for every $jin1,ldots,k_i$, is a dynamic $H$-trail if $W$ does not repeat edges and $c(e_i^{k_i})c(e_{i+1}^1)$ is an edge in $H$, for each $iin0,ldots,n-2$. In particular a dynamic $H$-trail is an alternating Euler trail when $H$ is a complete graph without loops and $k_i=1$, for every $iin1,ldots,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, $L_2^H(G)$, in a closed dynamic H-trail in $G$, and vice versa, where $L_2^H(G)$ is a non-colored simple graph obtained from $G$ in a polynomial time.

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Euler dynamic H-trails in edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404348)