Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652363 | Electronic Notes in Discrete Mathematics | 2009 | 5 Pages |
Abstract
We prove the following approximate version of Pósa's theorem for directed graphs: every directed graph on n vertices whose in- and outdegree sequences satisfy and for all i⩽n/2 has a Hamilton cycle. In fact, we prove that such digraphs are pancyclic (i.e. contain cycles of lengths 2,…,n). We also prove an approximate version of Chvátal's theorem for digraphs. This asymptotically confirms conjectures of Nash-Williams from 1968 and 1975.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics