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

Abstract

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

How to cite

top

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 -

References

top
  1. [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. [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. [3] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs, Fifth Edition (Chapman & Hall/CRC, Boca Raton, FL, 2011). 
  4. [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. [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. [6] R. Jones, K. Kolasinski and P. Zhang, On Hamiltonian-colored graphs, Util. Math. to appear. Zbl1293.05109
  7. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.