The exact digirth and out-degree bounds for C(k,k)-subdivision and out-forest in digraphs
Abstract
For each integer k≥2, let C(k,k) denote the oriented cycle formed by two internally vertex-disjoint directed paths of length k with the same initial and terminal vertices. Picasarri-Arrieta and Rambaud ({\small European J. Combin., 2024}) asked for the smallest integer gk such that every digraph with minimum out-degree at least two and digirth at least gk contains a subdivision of C(k,k). We completely resolve this problem by proving that gk=k+1. Our proof relies on a refinement of Thomassen's theorem ({\small Discrete Math., 1985}) on two directed cycles intersecting in exactly one vertex: we prove that every digraph with minimum out-degree at least two contains two directed cycles intersecting in exactly one arc. We also establish an embedding theorem for out-forests with prescribed images of their roots, under minimum out-degree and digirth conditions determined by the number of leaves and the heights of vertices in antichains. As an application, for integers k,ℓ≥2, we show that every digraph with minimum out-degree at least k and digirth at least k(ℓ−1)+1 contains k directed paths of length ℓ sharing only their initial vertex, which can be prescribed arbitrarily. This improves the previous digirth bound (kℓ−1)/(k−1)+1 of Picasarri-Arrieta and Rambaud to a sharp bound.
Related
- Sharp digirth bounds for C(k,k)-subdivisions in digraphs
- Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
- An Exact Dominant Degree Condition for Transitive Tournament Factors in Digraphs
- Degree conditions for k-strong orientations of digraphs
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
BibTeX
@misc{chen2026exact,
title = {{The exact digirth and out-degree bounds for $C(k,k)$-subdivision and out-forest in digraphs}},
author = {Bin Chen and Jianfeng Hou and Xinmin Hou and Siyue Liu and Xinjie Wang and Xinyu Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38574},
eprint = {2610.38574},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38574},
}
RIS
TY - UNPB
TI - The exact digirth and out-degree bounds for C(k,k)-subdivision and out-forest in digraphs
AU - Bin Chen
AU - Jianfeng Hou
AU - Xinmin Hou
AU - Siyue Liu
AU - Xinjie Wang
AU - Xinyu Zhou
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38574
UR - https://arxiv.org/abs/2610.38574
AB - For each integer k≥2, let C(k,k) denote the oriented cycle formed by two internally vertex-disjoint directed paths of length k with the same initial and terminal vertices. Picasarri-Arrieta and Rambaud ({\small European J. Combin., 2024}) asked for the smallest integer g_k such that every digraph with minimum out-degree at least two and digirth at least g_k contains a subdivision of C(k,k). We completely resolve this problem by proving that g_k=k+1. Our proof relies on a refinement of Thomassen's theorem ({\small Discrete Math., 1985}) on two directed cycles intersecting in exactly one vertex: we prove that every digraph with minimum out-degree at least two contains two directed cycles intersecting in exactly one arc. We also establish an embedding theorem for out-forests with prescribed images of their roots, under minimum out-degree and digirth conditions determined by the number of leaves and the heights of vertices in antichains. As an application, for integers k,ℓ≥2, we show that every digraph with minimum out-degree at least k and digirth at least k(ℓ−1)+1 contains k directed paths of length ℓ sharing only their initial vertex, which can be prescribed arbitrarily. This improves the previous digirth bound (k^ℓ−1)/(k−1)+1 of Picasarri-Arrieta and Rambaud to a sharp bound.
ER -