Hamiltonian degree sequences in digraphs
From MaRDI portal
Publication:974465
DOI10.1016/J.JCTB.2009.11.004zbMATH Open1209.05138arXiv0807.1827OpenAlexW2018724658MaRDI QIDQ974465FDOQ974465
Authors: Daniela Kühn, Deryk Osthus, Andrew Treglown 
Publication date: 3 June 2010
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0807.1827
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
Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45)
Cites Work
- On Hamilton's ideals
- Embedding large subgraphs into dense graphs
- Title not available (Why is that?)
- Testing subgraphs in directed graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Title not available (Why is that?)
- Title not available (Why is that?)
- An exact minimum degree condition for Hamilton cycles in oriented graphs
- Title not available (Why is that?)
- Hamilton Cycles in Oriented Graphs
- Title not available (Why is that?)
- Triangle packings and 1-factors in oriented graphs
- An Ore-type condition implying a digraph to be pancyclic
- A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
- Cycles in digraphs– a survey
- Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cycles of given length in oriented graphs
- A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
- Title not available (Why is that?)
Cited In (33)
- Path decompositions of tournaments
- The robust component structure of dense regular graphs and applications
- Title not available (Why is that?)
- Cycle partitions of regular graphs
- Hamilton cycles in dense regular digraphs and oriented graphs
- Hamilton decompositions of regular expanders: applications
- An approximate version of Sumner's universal tournament conjecture
- Monochromatic cycle partitions of graphs with large minimum degree
- Enumeration of the Degree Sequences of Line-Hamiltonian Multigraphs
- Embedding spanning bipartite graphs of small bandwidth
- A semiexact degree condition for Hamilton cycles in digraphs
- A rainbow Dirac's theorem
- Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
- A survey on Hamilton cycles in directed graphs
- Hamilton cycles and degree sequences
- A proof of Sumner's universal tournament conjecture for large tournaments
- Optimal packings of bounded degree trees
- Degree sequences forcing Hamilton cycles in directed graphs
- On the chromatic number of matching Kneser graphs
- Hamilton cycles in sparse robustly expanding digraphs
- Title not available (Why is that?)
- Proof of the 1-factorization and Hamilton Decomposition Conjectures
- Hamilton cycles in quasirandom hypergraphs
- Counting and packing Hamilton cycles in dense graphs and oriented graphs
- On forcibly \(k\)-connected and forcibly \(k\)-arc-connected digraphic sequences
- Crux, space constraints and subdivisions
- Solution to a problem of Bollobás and Häggkvist on Hamilton cycles in regular graphs
- A note on subdigraphs of digraphs with large outdegrees
- A generalization of a theorem of Nash-Williams
- Title not available (Why is that?)
- On sufficient conditions for spanning structures in dense graphs
- The Hamiltonian property of the consecutive-3 digraphs
- Optimal packings of Hamilton cycles in graphs of high minimum degree
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)
