The number of vertices of degree k in a minimally k ‐edge‐connected digraph

Let k be a positive integer, and D = ( V ( D ), E ( D )) be a minimally k ‐edge‐connected simple digraph. We denote the outdegree and indegree of x ∈ V ( D ) by δ D ( x ) and ρ D ( x ), respectively. Let u + ( D ) denote the number of vertices x in D with δ D ( x ) = k , ρ D ( x ) > k ; u ± ( D ) the number of vertices x with δ D ( x ) = ρ D ( x ) = k ; u − ( D ) the number of vertices x with δ D ( x ) > k , ρ D ( x ) = k . W. Mader asked the following question in [Mader, in Paul Erdös is Eighty, Keszthely, Budapest, 1996]: for each k ≥ 4, is there a c k > 0 such that u + ( D ) + 2 u ± ( D ) + u − ( D ) ≥ c k | D | holds? where | D | denotes the number of the vertices of D . In this article, we give a partial result for the question. It is proved that, for | D | ≥ 2 k − 2,$$u^{+}(D) + 2u^\pm(D)+u^-(D) \ge \cases{{2\left[D\right] \over 3k+2} + {4k^2+4 \over 3k+2} {\ \ \ \ {\rm for}\ k\ \ge 6},\cr\cr {\left[D\right] + 24 \over 7}{\indent\indent \ {\rm for}\ k\ = 4,}\cr\cr {2\left[D\right] + 80 \over 17}{\indent\indent {\rm for}\ k\ = 5.}}$$ © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 94–108, 2000