The number of vertices of degree k in a minimally k-edge-connected digraph
Yuan Xu-dong, Kang Liying, Mao-cheng Cai · Journal of Graph Theory · 2000
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 ck > 0 such that u+(D) + 2u±(D) + u−(D) ≥ ck|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| ≥ 2k − 2, © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 94–108, 2000