Limits on connections in minimal strong networks with given size
Sharp bounds and extremal structure of minimally strongly $k$-connected digraphs
Discrete Mathematics
Summary
This paper looks at networks where every node is connected strongly in at least k different ways, and removing any connection breaks that property. The authors find exact limits on how many connections such a network can have based on its size and the strength level k. They also show which networks reach these limits and prove earlier guesses by another researcher were correct. This helps understand the structure of these minimal strong networks more precisely.
What this means in practice
- •For network architects: Design minimal strong communication networks with known maximum link counts to optimize connectivity cost trade-offs.
- •For compiler optimizers: Use exact bounds on strongly connected digraphs to optimize control flow graph analyses in program transformations.
A theory result. No direct application yet.
Authors
Junran Yu, Gregory Gutin, Hong-Jian Lai, Xiaoyan Zhang
Abstract
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).