Extremal Problems for the Family of k-Strongly Connected Digraphs
Pith reviewed 2026-05-09 14:55 UTC · model grok-4.3
The pith
The saturation number sat(n, D_k) for the family of k-strongly connected digraphs equals exactly (k-1)(2n-k) + binom(n-k+1,2).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors prove that sat(n, D_k) equals (k-1)(2n-k) + binom(n-k+1,2). They further show that ex(n, D_k) is at most binom(n-k+1,2) + (17/6)(k-1)(n-k+1) for all n at least 3(k-1), and they conjecture that ex(n, D_k) equals binom(n,2) + (3/2)(k - 4/3)(n-k+1) for all sufficiently large n.
What carries the argument
The saturation number sat(n, D_k) and extremal number ex(n, D_k) defined for the family D_k of all k-strongly connected digraphs, which measure the min and max arcs among n-vertex digraphs that contain no member of D_k yet become members of D_k upon addition of any arc.
If this is right
- The exact saturation formula holds for every n and k.
- The maximum arc count in a saturated digraph is bounded above by a quadratic term plus a linear term in n when n meets the size condition.
- The conjectured exact extremal number would fix the densest possible saturated digraphs for all large n.
- The results classify the arc thresholds separating digraphs that avoid k-strong connectivity from those that force it.
Where Pith is reading between the lines
- The same saturation and extremal questions could be posed for k-arc-strongly connected digraphs using analogous constructions.
- The explicit formulas suggest that the extremal saturated digraphs consist of one dense block on roughly n-k+1 vertices with limited connections to the remaining vertices.
Load-bearing premise
The proofs rest on the standard definition of k-strong connectivity via k vertex-disjoint directed paths between every pair of vertices together with the existence of saturated digraphs achieving the stated arc counts.
What would settle it
An n-vertex digraph with fewer than (k-1)(2n-k) + binom(n-k+1,2) arcs that is still saturated with respect to D_k would falsify the saturation formula.
read the original abstract
Let $\mathcal{D}$ be a family of digraphs. A digraph $D$ is \emph{$\mathcal{D}$-saturated} if it contains no member of $\mathcal{D}$ as a subdigraph, but for any arc $e$ in the complement of $D$, the digraph $D + e$ contains some member of $\mathcal{D}$ as a subdigraph. The \emph{saturation number} $\mathrm{sat}(n,\mathcal{D})$ and the \emph{extremal number} $\mathrm{ex}(n,\mathcal{D})$ are the minimum number and the maximum number of arcs among all $n$-vertex $\mathcal{D}$-saturated digraphs. For a positive integer $k$, let $\mathcal{D}_k$ denote the family of \emph{$k$-strongly connected digraphs}. In this paper, firstly, we prove that $$\mathrm{sat}(n,\mathcal{D}_k)=(k-1)(2n-k)+\binom{n-k+1}{2}.$$ Then for $n\geq 3(k-1)$, we prove that $$\mathrm{ex}(n,\mathcal{D}_k)\leq \binom{n-k+1}{2}+\frac{17}{6}(k-1)(n-k+1).$$ In addition, we conjecture that for sufficiently large $n$, $$\mathrm{ex}(n,\mathcal{D}_k)=\binom{n}{2}+\frac{3}{2}(k-\frac{4}{3})(n-k+1).$$
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that the saturation number sat(n, D_k) equals (k-1)(2n-k) + binom(n-k+1,2) for the family D_k of k-strongly connected digraphs. It also proves the upper bound ex(n, D_k) ≤ binom(n-k+1,2) + (17/6)(k-1)(n-k+1) for all n ≥ 3(k-1), and conjectures that ex(n, D_k) = binom(n,2) + (3/2)(k - 4/3)(n-k+1) for sufficiently large n.
Significance. If the proofs hold, the work advances extremal digraph theory by giving an exact saturation number achieved via an explicit construction (complete bidirected graph on n-k+1 vertices plus k-1 vertices with prescribed in- and out-arcs) together with a matching lower bound from a standard counting argument on arcs that force k-strong connectivity. The upper bound on ex follows from a structural case analysis that partitions vertices by connectivity roles and applies double counting to reverse arcs, with the 17/6 coefficient obtained by optimizing a linear-programming relaxation over possible 2-cycles. These are standard, verifiable techniques in the area.
minor comments (2)
- The conjecture is stated for 'sufficiently large n' without an explicit threshold; adding even a qualitative remark on the required size of n would improve readability.
- In the proof of the upper bound, the transition from the case analysis to the LP relaxation over the number of 2-cycles could be expanded by one sentence to make the origin of the 17/6 coefficient fully transparent to readers.
Simulated Author's Rebuttal
We thank the referee for the careful reading of our manuscript and for the positive assessment, including the accurate summary of our results on the saturation number sat(n, D_k) and the upper bound on ex(n, D_k). We are pleased that the significance of the explicit construction and the structural case analysis is recognized. We address the report below.
Circularity Check
No circularity: direct combinatorial proofs via construction and case analysis
full rationale
The saturation number is obtained from an explicit D_k-saturated construction (complete bidirected graph on n-k+1 vertices plus k-1 vertices with specified arcs) whose arc count matches the claimed formula, with the lower bound following from a standard counting argument that any D_k-saturated digraph must contain at least that many arcs to ensure adding any missing arc creates a k-strongly connected subdigraph. The upper bound on ex(n,D_k) for n >= 3(k-1) follows from structural case analysis on maximal D_k-saturated digraphs, vertex partitioning by connectivity roles, double counting of reverse arcs, and optimization of a linear program over 2-cycles yielding the 17/6 coefficient; this is independent of the saturation formula and does not reduce to any fitted parameter or self-referential definition. The conjecture is stated separately without relying on the proved bounds. No self-citations are load-bearing, no ansatz is smuggled, and no quantity is renamed as a prediction. The derivation chain is self-contained against the standard definitions of k-strong connectivity and D-saturation.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Standard definitions of k-strong connectivity and the saturation property for digraph families.
Reference graph
Works this paper leans on
-
[1]
J. Anderson, H.-J. Lai, X. X. Lin, M. R. Xu,Onk-maximal strength digraphs,Journal of Graph Theory84(1) (2016) 17–25
work page 2016
-
[2]
J. Bang-Jensen, G. Gutin,Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer-Verlag, London, 2009
work page 2009
-
[3]
A. Bernshteyn, A. Kostochka,On the number of edges in a graph with no(k+ 1)-connected subgraphs,Discrete Mathematics339(2) (2016) 682–688
work page 2016
-
[4]
P. Erd˝ os, A. Hajnal, J. W. Moon,A problem in graph theory,The American Mathematical Monthly71(10) (1964) 1107–1110
work page 1964
-
[5]
Lai,The size of strength-maximal graphs,Journal of Graph Theory14(2) (1990) 187–197
H.-J. Lai,The size of strength-maximal graphs,Journal of Graph Theory14(2) (1990) 187–197
work page 1990
-
[6]
H. Lei, S. O, Y. T. Shi, D. B. West, X. D. Zhu,Extremal problems on saturation for the family ofk-edge-connected graphs,Discrete Applied Mathematics260(2019) 278–283
work page 2019
-
[7]
X. X. Lin, S. H. Fan, H.-J. Lai, M. R. Xu,On the lower bound ofk-maximal digraphs, Discrete Mathematics339(10) (2016) 2500–2510. 16
work page 2016
-
[8]
Mader,Minimalen-fach kantenzusammenh¨ angende Graphen,Mathematische Annalen 191(1971) 21–28
W. Mader,Minimalen-fach kantenzusammenh¨ angende Graphen,Mathematische Annalen 191(1971) 21–28
work page 1971
-
[9]
W. Mader,Existenzn-fach zusammenh¨ angender Teilgraphen in Graphen gen¨ ugend großen Kantendichte,Abhandlungen aus dem Mathematischen Seminar der Universit¨ at Hamburg 37(1972) 86–97
work page 1972
-
[10]
Mader,Connectivity and edge-connectivity in finite graphs, In: B
W. Mader,Connectivity and edge-connectivity in finite graphs, In: B. Bollob´ as (ed.),Sur- veys in Combinatorics, London Mathematical Society Lecture Note Series, Vol. 38, Cam- bridge University Press, Cambridge, 1979, pp. 66–95
work page 1979
-
[11]
D. J. Rose,On simple characterizations ofk-trees,Discrete Mathematics7(1974) 317–322
work page 1974
-
[12]
Tur´ an,Eine Extremalaufgabe aus der Graphentheorie,Matematikai ´ es Fizikai Lapok48 (1941) 436–452
P. Tur´ an,Eine Extremalaufgabe aus der Graphentheorie,Matematikai ´ es Fizikai Lapok48 (1941) 436–452
work page 1941
-
[13]
P. Wenger,A note on the saturation number of the family ofk-connected graphs,Discrete Mathematics323(2014) 81–83
work page 2014
-
[14]
L. Q. Xu, H.-J. Lai, Y. Z. Tian,On the extremal sizes of maximal graphs without(k+ 1)- connected subgraphs,Discrete Applied Mathematics285(2020) 397–406
work page 2020
-
[15]
Yuster,A note on graphs withoutk-connected subgraphs,Ars Combinatoria67(2003) 231–235
R. Yuster,A note on graphs withoutk-connected subgraphs,Ars Combinatoria67(2003) 231–235. 17
work page 2003
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.