Hamiltonian-colored powers of strong digraphs

Garry Johns, et al. "Hamiltonian-colored powers of strong digraphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 705-724. <http://eudml.org/doc/271043>.

@article{GarryJohns2012,
abstract = {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.},
author = {Garry Johns, Ryan Jones, Kyle Kolasinski, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {powers of a strong oriented graph; distance-colored digraphs; Hamiltonian-colored digraphs; Hamiltonian coloring exponents},
language = {eng},
number = {4},
pages = {705-724},
title = {Hamiltonian-colored powers of strong digraphs},
url = {http://eudml.org/doc/271043},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Garry Johns
AU - Ryan Jones
AU - Kyle Kolasinski
AU - Ping Zhang
TI - Hamiltonian-colored powers of strong digraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 705
EP - 724
AB - 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.
LA - eng
KW - powers of a strong oriented graph; distance-colored digraphs; Hamiltonian-colored digraphs; Hamiltonian coloring exponents
UR - http://eudml.org/doc/271043
ER -