Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: distance-colored digraphs

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Hamiltonian-colored powers of strong digraphs

100%

Johns G., Jones R., Kolasinski K., Zhang P.

Discussiones Mathematicae Graph Theory

2012

tom 32

nr 4

705-724

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Johns G.

1 Jones R.

1 Kolasinski K.

1 Zhang P.

1 2012

Wyniki wyszukiwania

Hamiltonian-colored powers of strong digraphs