Hamiltonian-colored powers of strong digraphs

Johns, Garry ; Jones, Ryan ; Kolasinski, Kyle ; Zhang, Ping

Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 705-724

Résumé

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ₙ 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ₖ such that hce(Dₖ) = k with the added property that every properly colored Hamiltonian cycle in the kth power of Dₖ 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.

Détail

Keywords: powers of a strong oriented graph, distance-colored digraphs, Hamiltonian-colored digraphs, Hamiltonian coloring exponents