| Texto completo | |
| Autor(es): |
Stein, Maya
;
Zarate-Gueren, Camila
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | COMBINATORICS PROBABILITY & COMPUTING; v. N/A, p. 21-pg., 2024-03-06. |
| Resumo | |
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 Thomasse 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$ . (AU) | |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |