Antidirected forests in digraphs
Abstract
A digraph is antidirected if every vertex has indegree zero or outdegree zero. Let k≥2, and let F be an antidirected forest with k arcs and no isolated vertices. We prove that every digraph D of order n with more than gk(n):=2max{binom2k−12, (k−1)(n−k/2)} arcs contains F as a subdigraph. For n≥2k−1, this threshold equals 2ex(n,kK2) and is attained by symmetric digraphs arising from extremal kK2-free graphs. Consequently, the maximum directed extremal number over all such forests is 2ex(n,kK2). The proof combines a counting inequality for rooted antidirected forests, embeddings extending vertex-disjoint arcs, and vertex deletion. In the remaining case, the Gallai--Edmonds decomposition of the underlying graph gives the required bound on the number of arcs.
Related
BibTeX
@misc{liu2026antidirected,
title = {{Antidirected forests in digraphs}},
author = {Gengtao Liu and Yunshu Gao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18469},
eprint = {2609.18469},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18469},
}
RIS
TY - UNPB
TI - Antidirected forests in digraphs
AU - Gengtao Liu
AU - Yunshu Gao
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18469
UR - https://arxiv.org/abs/2609.18469
AB - A digraph is antidirected if every vertex has indegree zero or outdegree zero. Let k≥2, and let F be an antidirected forest with k arcs and no isolated vertices. We prove that every digraph D of order n with more than g_k(n):=2max{binom2k−12, (k−1)(n−k/2)} arcs contains F as a subdigraph. For n≥2k−1, this threshold equals 2ex(n,kK_2) and is attained by symmetric digraphs arising from extremal kK_2-free graphs. Consequently, the maximum directed extremal number over all such forests is 2ex(n,kK_2). The proof combines a counting inequality for rooted antidirected forests, embeddings extending vertex-disjoint arcs, and vertex deletion. In the remaining case, the Gallai--Edmonds decomposition of the underlying graph gives the required bound on the number of arcs.
ER -