On Hamiltonian Powers of Digraphs |
| |
Authors: | Antoni Marczyk |
| |
Institution: | (1) Faculty of Applied Mathematics AGH, Al. Mickiewicza 30, 30-059 Kraków, Poland e-mail: marczyk@ui.agh.edu.pl, PL |
| |
Abstract: | For a strongly connected digraph D, the k-th power D
k of D is the digraph with the same set of vertices, a vertex x being joined to a vertex y in D
k if the directed distance from x to y in D is less than or equal to k. It follows from a result of Ghouila-Houri that for every digraph D on n vertices and for every k≥n/2, D
k is hamiltonian. In the paper we characterize these digraphs D of odd order whose (⌈n/2 ⌉−1)-th power is hamiltonian.
Revised: June 13, 1997 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|