Abstract: We show that for each eta>0 every digraph G of sufficiently large order n is Hamiltonian if its out- and indegree sequences d^+_1le ... le d^+_n and d^- _1 le ... le d^-_n satisfy (i) d^+_i geq i+ eta n or d^-_{n-i- eta n} geq n-i and (ii) d^-_i geq i+ eta n or d^+_{n-i- eta n} geq n-i for all i < n/2. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chv'atal's theorem. In fact, we prove the stronger result that such digraphs G are pancyclic.
Recommendations
- A semiexact degree condition for Hamilton cycles in digraphs
- Powers of Hamilton cycles in tournaments
- scientific article; zbMATH DE number 1109394
- Degree sequences forcing Hamilton cycles in directed graphs
- An approximate version of Jackson's conjecture
- scientific article; zbMATH DE number 3952812
- Hamilton decompositions of regular tournaments
- Hamiltonian degree conditions for tough graphs
- scientific article; zbMATH DE number 5371651
- scientific article; zbMATH DE number 773235
Cites work
- scientific article; zbMATH DE number 3149611 (Why is no real title available?)
- scientific article; zbMATH DE number 3508537 (Why is no real title available?)
- scientific article; zbMATH DE number 3632516 (Why is no real title available?)
- scientific article; zbMATH DE number 1067836 (Why is no real title available?)
- scientific article; zbMATH DE number 863469 (Why is no real title available?)
- scientific article; zbMATH DE number 3303831 (Why is no real title available?)
- scientific article; zbMATH DE number 3310759 (Why is no real title available?)
- scientific article; zbMATH DE number 3186565 (Why is no real title available?)
- A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
- A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
- An Ore-type condition implying a digraph to be pancyclic
- An exact minimum degree condition for Hamilton cycles in oriented graphs
- Cycles in digraphs– a survey
- Cycles of given length in oriented graphs
- Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
- Embedding large subgraphs into dense graphs
- Hamilton Cycles in Oriented Graphs
- On Hamilton's ideals
- Testing subgraphs in directed graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Triangle packings and 1-factors in oriented graphs
Cited in
(33)- Embedding spanning bipartite graphs of small bandwidth
- Hamilton decompositions of regular expanders: applications
- A note on subdigraphs of digraphs with large outdegrees
- The robust component structure of dense regular graphs and applications
- Optimal packings of bounded degree trees
- Proof of the 1-factorization and Hamilton Decomposition Conjectures
- Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
- An approximate version of Sumner's universal tournament conjecture
- Counting and packing Hamilton cycles in dense graphs and oriented graphs
- Hamilton cycles in quasirandom hypergraphs
- scientific article; zbMATH DE number 853076 (Why is no real title available?)
- scientific article; zbMATH DE number 27748 (Why is no real title available?)
- Cycle partitions of regular graphs
- The Hamiltonian property of the consecutive-3 digraphs
- Hamilton cycles and degree sequences
- A semiexact degree condition for Hamilton cycles in digraphs
- Hamilton cycles in dense regular digraphs and oriented graphs
- A proof of Sumner's universal tournament conjecture for large tournaments
- A survey on Hamilton cycles in directed graphs
- A rainbow Dirac's theorem
- Degree sequences forcing Hamilton cycles in directed graphs
- Hamilton cycles in sparse robustly expanding digraphs
- On forcibly \(k\)-connected and forcibly \(k\)-arc-connected digraphic sequences
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- Monochromatic cycle partitions of graphs with large minimum degree
- On the chromatic number of matching Kneser graphs
- Crux, space constraints and subdivisions
- scientific article; zbMATH DE number 1536526 (Why is no real title available?)
- A generalization of a theorem of Nash-Williams
- Optimal packings of Hamilton cycles in graphs of high minimum degree
- Path decompositions of tournaments
- Enumeration of the Degree Sequences of Line-Hamiltonian Multigraphs
- On sufficient conditions for spanning structures in dense graphs
This page was built for publication: Hamiltonian degree sequences in digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974465)
