| مستخلص: |
Let H be a graph possibly with loops and G be a multigraph without loops. An H-coloring of G is a function c : E (G) → V (H) . We will say that G is an H-colored multigraph, whenever we are taking a fixed H-coloring of G. The set of all the edges with end vertices u and v will be denoted by E uv . We will say that W = (v 0 , e 0 1 , ... , e 0 k 0 , v 1 , e 1 1 , ... , e 1 k 1 , v 2 , ... , v n - 1 , e n - 1 1 , ... , e n - 1 k n - 1 , v n) , where for each i in { 0 , ... , n - 1 } , k i ≥ 1 and e i j ∈ E v i v i + 1 for every j ∈ { 1 , ... , k i } , is a dynamic H-walk iff c (e i k i) c (e i + 1 1) is an edge in H, for each i ∈ { 0 , ... , n - 2 } . We will say that a dynamic H-walk is a closed dynamic H-walk whenever v 0 = v n and c (e n - 1 k n - 1 ) c (e 0 1) is an edge in H. Moreover, a closed dynamic H-walk is called dynamic H-cycle whenever v i ≠ v j , for every { i , j } ⊆ { 0 , ... , v n - 1 } . In particular, a dynamic H-walk is an H-walk whenever k i = 1 , for every i ∈ { 0 , ... , n - 1 } , and when H is a complete graph without loops, an H-walk is well known as a properly colored walk. In this work, we study the existence and length of dynamic H-cycles, dynamic H-trails and dynamic H-paths in H-colored multigraphs. To accomplish this, we introduce a new concept of color degree, namely, the dynamic degree, which allows us to extend some classic results, as Ore's Theorem, for H-colored multigraphs. Also, we give sufficient conditions for the existence of hamiltonian dynamic H-cycles in H-colored multigraphs, and as a consequence, we obtain sufficient conditions for the existence of properly colored hamiltonian cycle in edge-colored multigraphs, with at least c ≥ 3 colors. [ABSTRACT FROM AUTHOR] |