Degree conditions for k-strong orientations of digraphs
Abstract
Jackson and Thomassen conjectured that every 2k-strong digraph contains a spanning k-strong oriented subdigraph. We prove sharp degree conditions for the existence of such a subdigraph. For every fixed positive integer k and all sufficiently large n, every n-vertex digraph D with δ0(D)≥⌊(n+k−1)/2⌋ admits a k-strong orientation. This threshold is best possible even for the weaker conclusion that D itself is k-strong. We also prove a sharp Woodall-type analogue for every fixed positive integer k and all sufficiently large n: if dD+(x)+dD-(y)≥ n+2k−2 for every missing arc xy, then D admits a k-strong orientation, and this bound is again best possible. As a further consequence, we determine the sharp minimum total degree threshold. Finally, the semi-degree result also remains valid when k≤αn for every fixed 0<α<0.094882….
Related
- Dominant-Degree Conditions for Ramsey--Turán Factors of Non-Directed Cycle Orientations
- Avoidability of Digraphs with Height Functions and Orientations of C4
- Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
- An Exact Dominant Degree Condition for Transitive Tournament Factors in Digraphs
- The exact digirth and out-degree bounds for C(k,k)-subdivision and out-forest in digraphs
BibTeX
@misc{bangjensen2026degree,
title = {{Degree conditions for $k$-strong orientations of digraphs}},
author = {Jørgen Bang-Jensen and Shuo Wei},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36551},
eprint = {2609.36551},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36551},
}
RIS
TY - UNPB
TI - Degree conditions for k-strong orientations of digraphs
AU - Jørgen Bang-Jensen
AU - Shuo Wei
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36551
UR - https://arxiv.org/abs/2609.36551
AB - Jackson and Thomassen conjectured that every 2k-strong digraph contains a spanning k-strong oriented subdigraph. We prove sharp degree conditions for the existence of such a subdigraph. For every fixed positive integer k and all sufficiently large n, every n-vertex digraph D with δ^0(D)≥⌊(n+k−1)/2⌋ admits a k-strong orientation. This threshold is best possible even for the weaker conclusion that D itself is k-strong. We also prove a sharp Woodall-type analogue for every fixed positive integer k and all sufficiently large n: if d_D^+(x)+d_D^-(y)≥ n+2k−2 for every missing arc xy, then D admits a k-strong orientation, and this bound is again best possible. As a further consequence, we determine the sharp minimum total degree threshold. Finally, the semi-degree result also remains valid when k≤αn for every fixed 0<α<0.094882….
ER -