2610.14979

Total: 1

#1 Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs [PDF] [Copy] [Kimi] [REL]

Authors: Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang

Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).

Subjects: Combinatorics , Discrete Mathematics

Publish: 2026-10-10 14:52:53 UTC