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

被引:0
作者
Yuan, XD [1 ]
Kang, LY [1 ]
Cai, MC [1 ]
机构
[1] Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
关键词
k-edge-connected; degree; tree representation;
D O I
10.1002/(SICI)1097-0118(200002)33:23.0.CO;2-I
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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 is an element of V(D) by delta(D)(x) and rho(D)(x), respectively. Let uf(D) denote the number of vertices x in D with delta(D) (x) = k, rho(D)(x) > k; u(+/-)(D) the number of vertices x with delta(D) (x) = rho(D)(x) = k;u(-)(D) the number of vertices x with delta(D)(x) > k, rho(D)(x) = k. W. Mader asked the following question in [Mader, in Paul Erdos is Eighty, Keszthely, Budapest, 1996]. for each k greater than or equal to 4, is there a c(k) > 0 such that u(+)(D) + 2u(+/-)(D) + u(-)(D) greater than or equal to 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\ greater than or equal to 2k - 2, [GRAPHICS] (C) 2000 John Wiley & Sons, Inc.
引用
收藏
页码:94 / 108
页数:15
相关论文
共 7 条