Back to Search
Start Over
Antidirected subgraphs of oriented graphs.
- Source :
- Combinatorics, Probability & Computing; Sep2024, Vol. 33 Issue 4, p1-21, 21p
- Publication Year :
- 2024
-
Abstract
- We show that for every $\eta \gt 0$ every sufficiently large $n$ -vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta)\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs. Further, we show that in the same setting, $D$ contains every $k$ -edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$. Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$ -vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09635483
- Volume :
- 33
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Combinatorics, Probability & Computing
- Publication Type :
- Academic Journal
- Accession number :
- 181512174
- Full Text :
- https://doi.org/10.1017/S0963548324000038