×

On Hamiltonian-colored graphs. (English) Zbl 1293.05109

Summary: For a connected graph \(G\) and a positive integer \(k\), the \(k\)th power \(G^k\) of \(G\) is the graph with \(V(G^k)= V(G)\), where \(uv\in 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^2\) 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 \(\text{hce}(G)\).
It is shown that for each pair \(k\), \(d\) of integers with \(4\leq k\leq d\), there exists a tree \(T\) with \(\text{hce}(T)= k\) and \(\text{diam}(T)= d\). Hamiltonian coloring exponents are determined for several well-known classes of trees. It is also shown that for each integer \(k\geq 2\), there exists a tree \(T_k\) with \(\text{hce}(T_k)= k\) such that every properly colored Hamiltonian cycle in the \(k\)th power of \(T_k\) must use all colors \(1,2,\dots, k\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite