GT 32/4

Discussiones Mathematicae Graph Theory 32(4) (2012) 705-724
doi: 10.7151/dmgt.1636

Hamiltonian-colored Powers of Strong Digraphs

Garry Johns¹, Ryan Jones²,
Kyle Kolasinski² and Ping Zhang²

¹ Saginaw Valley State University
² Western Michigan University

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 ≥ #x23a1;n/2 #x23a4;, the digraph D^k is Hamiltonian and the lower bound #x23a1;n/2 #x23a4; 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.

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

2010 Mathematics Subject Classification: 05C12, 05C15, 05C20, 05C45.

References

[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.

Received 7 July 2011
Revised 10 December 2011
Accepted 21 December 2011