Hamiltonian degree sequences in digraphs

DOI10.1016/J.JCTB.2009.11.004zbMATH Open1209.05138arXiv0807.1827OpenAlexW2018724658MaRDI QIDQ974465FDOQ974465

Deryk Osthus, Andrew Treglown, Daniela Kühn

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

zbMATH Keywords

expansiondirected graphstournamentsHamilton cyclesdegree sequencesregularity Lemma

Mathematics Subject Classification ID

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 (31)

• A Rainbow Dirac's Theorem
• 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
• On the Chromatic Number of Matching Kneser Graphs
• Enumeration of the Degree Sequences of Line-Hamiltonian Multigraphs
• 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 Hamilton Cycles in Graphs of High Minimum Degree
• Optimal packings of bounded degree trees
• Degree sequences forcing Hamilton cycles in directed 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
• Optimal path and cycle decompositions of dense quasirandom graphs
• Title not available (Why is that?)
• On sufficient conditions for spanning structures in dense graphs
• The Hamiltonian property of the consecutive-3 digraphs
• Embedding Spanning Bipartite Graphs of Small Bandwidth

   Recommendations

• A semiexact degree condition for Hamilton cycles in digraphs 👍 👎
• Powers of Hamilton cycles in tournaments 👍 👎
• Title not available (Why is that?) 👍 👎
• Degree sequences forcing Hamilton cycles in directed graphs 👍 👎
• An approximate version of Jackson’s conjecture 👍 👎
• Title not available (Why is that?) 👍 👎
• Hamilton decompositions of regular tournaments 👍 👎
• Hamiltonian degree conditions for tough graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)