PreprintCC BY 4.0arXiv
Sharp bounds and extremal structure of minimally strongly k-connected digraphs
Abstract
Let D be a finite simple minimally strongly k-connected digraph, where k≥ 2, and let n=|V(D)|. Mader proved in 1985 that |A(D)|≤ 2k(n−k) for all sufficiently large n, with equality if and only if D≅ overleftrightarrowKk,n−k (JCTB 1985). We prove that this bound holds whenever n≥ 3k−1 and that the order threshold 3k−1 is best possible. Moreover, if n≥ 3k, then equality holds if and only if D≅ overleftrightarrowKk,n−k. The threshold 3k is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).
Related
- Eccentric Connectivity Index of Cartesian product and Strong product of Strongly Connected Digraphs
- Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
- Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs
- Highly connected uniquely k-linked digraphs
- Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
BibTeX
@misc{yu2026sharp,
title = {{Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs}},
author = {Junran Yu and Gregory Gutin and Hong-Jian Lai and Xiaoyan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14979},
eprint = {2610.14979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14979},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp bounds and extremal structure of minimally strongly k-connected digraphs
AU - Junran Yu
AU - Gregory Gutin
AU - Hong-Jian Lai
AU - Xiaoyan Zhang
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14979
UR - https://arxiv.org/abs/2610.14979
AB - Let D be a finite simple minimally strongly k-connected digraph, where k≥ 2, and let n=|V(D)|. Mader proved in 1985 that |A(D)|≤ 2k(n−k) for all sufficiently large n, with equality if and only if D≅ overleftrightarrowK_k,n−k (JCTB 1985). We prove that this bound holds whenever n≥ 3k−1 and that the order threshold 3k−1 is best possible. Moreover, if n≥ 3k, then equality holds if and only if D≅ overleftrightarrowK_k,n−k. The threshold 3k is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).
ER -