On Hamiltonian-colored graphs

Abstract

For a connected graph G and a positive integer k, the kth power G ^k of G is the graph with V(G^k) = V(G) where uv ⋯ E(G^k) if the distance d_G(u,v) between u and v is at most k. The edge coloring of G^k defined by assigning each edge uv of G^k the color d_G(u,v) produces an edge-colored graph G ^k called a distance-colored graph. A distance-colored graph G ^k is Hamiltonian-colored if G^k contains a properly colored Hamiltonian cycle. It is shown that for a complete multipartite graph G, the distance-colored graph G² is Hamiltonian-colored if and only if G is Hamiltonian and each partite set of G has an even number of vertices. The minimum k for which G^k is Hamiltonian-colored is the Hamiltonian coloring exponent hce(G). It is shown that for each pair k, d of integers with 4 ≤k≤d, there exists a tree T with hce(T) = k and diam(T) = d. Hamiltonian coloring exponents are determined for several well-known classes of trees. It is also shown that for each integer k≥ 2, there exists a tree T_k with hce(T_k) = k such that every properly colored Hamiltonian cycle in the kth power of T_k must use all colors 1,2,...,k.