Geodesic
Hamiltonian-colored powers of strong digraphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 705-724.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: powers of a strong oriented graph, distance-colored digraphs, Hamiltonian-colored digraphs, Hamiltonian coloring exponents 
@article{DMGT_2012_32_4_a7,
     author = {Johns, Garry and Jones, Ryan and Kolasinski, Kyle and Zhang, Ping},
     title = {Hamiltonian-colored powers of strong digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {705--724},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a7/}
}
TY  - JOUR
AU  - Johns, Garry
AU  - Jones, Ryan
AU  - Kolasinski, Kyle
AU  - Zhang, Ping
TI  - Hamiltonian-colored powers of strong digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 705
EP  - 724
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a7/
LA  - en
ID  - DMGT_2012_32_4_a7
ER  - 
%0 Journal Article
%A Johns, Garry
%A Jones, Ryan
%A Kolasinski, Kyle
%A Zhang, Ping
%T Hamiltonian-colored powers of strong digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 705-724
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a7/
%G en
%F DMGT_2012_32_4_a7
Johns, Garry; Jones, Ryan; Kolasinski, Kyle; Zhang, Ping. Hamiltonian-colored powers of strong digraphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 705-724. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a7/

[1] G. Chartrand, R. Jones, K. Kolasinski and P. Zhang, On the Hamiltonicity of distance-colored graphs, Congr. Numer. 202 (2010) 195-209.

[2] G. Chartrand, K. Kolasinski and P. Zhang, The colored bridges problem, Geographical Analysis 43 (2011) 370-382, doi: 10.1111/j.1538-4632.2011.00827.x.

[3] G. Chartrand, L. Lesniak and P. Zhang, Graphs Digraphs, Fifth Edition (Chapman Hall/CRC, Boca Raton, FL, 2011).

[4] H. Fleischner, The square of every nonseparable graph is Hamiltonian, Bull. Amer. Math. Soc. 77 (1971) 1052-1054, doi: 10.1090/S0002-9904-1971-12860-4.

[5] A. Ghouila-Houri, Une condition suffisante d'existence d'un circuit Hamiltonien, C. R. Acad. Sci. Paris 251 (1960) 495-497.

[6] R. Jones, K. Kolasinski and P. Zhang, On Hamiltonian-colored graphs, Util. Math. to appear.

[7] M. Sekanina, On an ordering of the set of vertices of a connected graph, Publ. Fac. Sci. Univ. Brno 412 (1960) 137-142.