Hamiltonian-colored powers of strong digraphs
Garry L. Johns, Ryan Jones, Kyle Kolasinski, Ping Zhang · Discussiones Mathematicae Graph Theory · 2012
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 D k if the directed distance d D (u, 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 D k is assigned the color i where i = d D (u, v).The digraph D k is Hamiltonian-colored if D k contains a properly arc-colored Hamiltonian cycle.The smallest positive integer k for which D k 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 C n of order n is determined whenever this number exists.It is shown for each integer k ≥ 2 that there exists a strong oriented graph D k such that hce(D k ) = k with the added property that every properly colored Hamiltonian cycle in the kth power of D k 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(D ′ ) ≥ p.