# Hamiltonian-colored powers of strong digraphs

Garry Johns; Ryan Jones; Kyle Kolasinski; Ping Zhang

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 4, page 705-724
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGarry 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 -

## References

top- [1] G. Chartrand, R. Jones, K. Kolasinski and P. Zhang, On the Hamiltonicity of distance-colored graphs, Congr. Numer. 202 (2010) 195-209. Zbl1229.05195
- [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. Zbl0223.05124
- [5] A. Ghouila-Houri, Une condition suffisante d'existence d'un circuit Hamiltonien, C. R. Acad. Sci. Paris 251 (1960) 495-497. Zbl0091.37503
- [6] R. Jones, K. Kolasinski and P. Zhang, On Hamiltonian-colored graphs, Util. Math. to appear. Zbl1293.05109
- [7] M. Sekanina, On an ordering of the set of vertices of a connected graph, Publ. Fac. Sci. Univ. Brno 412 (1960) 137-142.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.