The Library
Spanning trees in dense directed graphs
Tools
Tools
Tools
Kathapurkar, Amarja and Montgomery, Richard (2022) Spanning trees in dense directed graphs. Journal of Combinatorial Theory, Series B, 156 . pp. 223-249. doi:10.1016/j.jctb.2022.04.007 ISSN 0095-8956.
![[img]](https://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
WRAP-Spanning-trees-in-dense-directed-graphs-Montgomery-22.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only until 16 May 2024. Contact author directly, specifying your specific needs. - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (533Kb) |
Official URL: https://doi.org/10.1016/j.jctb.2022.04.007
Abstract
In 2001, Komlós, Sárközy and Szemerédi proved that, for each α>0, there is some c>0 and n0 such that, if n≥n0, then every n-vertex graph with minimum degree at least (1/2+α)n contains a copy of every n-vertex tree with maximum degree at most cn/logn. We prove the corresponding result for directed graphs. That is, for each α>0, there is some c>0 and n0 such that, if n≥n0, then every n-vertex directed graph with minimum semi-degree at least (1/2+α)n contains a copy of every n-vertex oriented tree whose underlying maximum degree is at most cn/logn.
As with Komlós, Sárközy and Szemerédi's theorem, this is tight up to the value of c. Our result improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most Δ, for any constant Δ∈N and sufficiently large n. In contrast to these results, our methods do not use Szemerédi's regularity lemma.
| Item Type: | Journal Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
| Library of Congress Subject Headings (LCSH): | Spanning trees (Graph theory), Directed graphs | |||||||||
| Journal or Publication Title: | Journal of Combinatorial Theory, Series B | |||||||||
| Publisher: | Elsevier | |||||||||
| ISSN: | 0095-8956 | |||||||||
| Official Date: | September 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 156 | |||||||||
| Page Range: | pp. 223-249 | |||||||||
| DOI: | 10.1016/j.jctb.2022.04.007 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Copyright Holders: | Elsevier | |||||||||
| Date of first compliant deposit: | 21 June 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
