PreprintarXiv licencearXiv
Sharp digirth bounds for C(k,k)-subdivisions in digraphs
Abstract
For an 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. We extend a problem of Picasarri-Arrieta and Rambaud [European J. Combin. 122 (2024)] on subdivisions of C(k,k) to digraphs with several vertices of out-degree one. Following the sharp result of Chen et al. [arXiv:2610.38574v1 (2026)] for at most one such vertex, we determine the exact digirth threshold when at most r≥4 such vertices are permitted. Specifically, for all integers k≥2 and r≥4, every digraph of minimum out-degree at least one, with at most r vertices of out-degree one and digirth at least r(k−1)+1, contains a subdivision of C(k,k).
Related
- The exact digirth and out-degree bounds for C(k,k)-subdivision and out-forest in digraphs
- Sharp bounds and extremal structure of minimally strongly k-connected digraphs
- Fractional majority coloring of digraphs: bounds and inapproximability
- Sharp Probabilistic Normwise Backward Error Bounds for LU Factorization
- Sharp Bounds for Limits of N-Point Correlation
BibTeX
@misc{zhang2026sharp,
title = {{Sharp digirth bounds for C(k,k)-subdivisions in digraphs}},
author = {Hao Zhang and Panpan Cheng and Jin Yan and Tong Zhou},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00720},
eprint = {2611.00720},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00720},
}
RIS
TY - UNPB
TI - Sharp digirth bounds for C(k,k)-subdivisions in digraphs
AU - Hao Zhang
AU - Panpan Cheng
AU - Jin Yan
AU - Tong Zhou
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00720
UR - https://arxiv.org/abs/2611.00720
AB - For an 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. We extend a problem of Picasarri-Arrieta and Rambaud [European J. Combin. 122 (2024)] on subdivisions of C(k,k) to digraphs with several vertices of out-degree one. Following the sharp result of Chen et al. [arXiv:2610.38574v1 (2026)] for at most one such vertex, we determine the exact digirth threshold when at most r≥4 such vertices are permitted. Specifically, for all integers k≥2 and r≥4, every digraph of minimum out-degree at least one, with at most r vertices of out-degree one and digirth at least r(k−1)+1, contains a subdivision of C(k,k).
ER -