On pancyclic digraphs |
| |
Authors: | Roland Häggkvist Carsten Thomassen |
| |
Institution: | Matematisk Institut, Aarhus Universitet, Aarhus, Denmark |
| |
Abstract: | We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs Kp,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|