HAMILTONIAN-COLORED POWERS OF STRONG DIGRAPHS

作者：Johns Garry^*; Jones Ryan; Kolasinski Kyle; Zhang Ping

来源：Discussiones Mathematicae - Graph Theory, 2012, 32(4): 705-724.

DOI：10.7151/dmgt.1636

• powers of a strong oriented graph
• distance-colored digraphs
• Hamiltonian-colored digraphs
• Hamiltonian coloring exponents

For a strong oriented graph D of order n and diameter d and an integer k with 1 <= k <= d, the kth power D-k of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of Dk if the directed distance v) from u to v in D is at most k. For every strong digraph D of order n >= 2 and every integer k >= [n/2], the digraph D-k is Hamiltonian and the lower bound [n/2] is sharp. The digraph D-k is distance-colored if each arc (u, v) of Dk is assigned the color i where i = (d) over right arrow (D)(u, v). The digraph D-k is Hamiltonian-colored if Dk contains a properly arc-colored Hamiltonian cycle. The smallest positive integer k for which Dk is Hamiltonian-colored is the Hamiltonian coloring exponent hce(D) of D. For each integer n >= 3, the Hamiltonian coloring exponent of the directed cycle 09,, of order n is determined whenever this number exists. It is shown for each integer k >= 2 that there exists a strong oriented graph Dk such that hce(Dk) = k with the added property that every properly colored Hamiltonian cycle in the kth power of Dk must use all k colors. It is shown for every positive integer p there exists a a connected graph G with two different strong orientations D and D' such that hce(D) hce(DI) >= p.

• 出版日期2012