
AbstractWe 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 12n(n + 1) – 3 edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least 12n(n + 1) – 1 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.
Extremal problems in graph theory, Computational Theory and Mathematics, Directed graphs (digraphs), tournaments, Discrete Mathematics and Combinatorics, Theoretical Computer Science
Extremal problems in graph theory, Computational Theory and Mathematics, Directed graphs (digraphs), tournaments, Discrete Mathematics and Combinatorics, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 37 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
