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

✍ Scribed by Yuan Xu-dong; Kang Liying; Cai Mao-cheng

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 298 KB
• Volume: 33
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(200002)33:2<94::aid-jgt4>3.0.co;2-i

✦ Synopsis

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

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) + 2u ± (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| ≥ 2k -2,

3k+2 for k ≥ 6, |D|+24 7

for k = 4, 2|D|+80 17

for k = 5.