Binding Numbers and Connected Factors

被引:10
作者
Nam, Yunsun [1 ]
机构
[1] Natl Inst Hlth, Ctr Genome Sci, Div Biomed Informat, Seoul 122701, South Korea
关键词
Connected factor; a; b]-Factor; Binding number; K-FACTORS; GRAPHS; EXISTENCE;
D O I
10.1007/s00373-010-0953-6
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, we obtain some sufficient conditions based on binding number for a graph to have a connected factor with degree restrictions. Let alpha and k be positive integers with alpha + k a parts per thousand yen 4. Let G be a connected graph with a spanning subgraph F, each component of which has order at least alpha. We show that if the binding number of G is greater than (alpha k - alpha)/(alpha k - alpha -1) (k a parts per thousand yen 2) and alpha/(alpha -2) (k = 1) then G has a connected subgraph which has F and in which every vertex v has degree at most deg (F) (v) + k. From the result, we derive various sufficient conditions for a graph to have a connected [a, b]-factor.
引用
收藏
页码:805 / 813
页数:9
相关论文
共 18 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]  
[Anonymous], 1993, SYST SCI MATH SCI
[3]  
BERGE C, 1978, P K NED AKAD A MATH, V81, P165
[4]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[5]  
CAI M, 1999, ELECT J COMBIN, V6
[6]   Connected [k,k+1]-factors of graphs [J].
Cai, MC .
DISCRETE MATHEMATICS, 1997, 169 (1-3) :1-16
[7]  
CHEN C, 1992, J SYS SCI MATH SCIS, V5, P141
[8]  
Ellingham MN, 2000, J GRAPH THEOR, V33, P125, DOI 10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.3.CO
[9]  
2-O
[10]   Connected (g, f)-factors [J].
Ellingham, MN ;
Nam, Y ;
Voss, HJ .
JOURNAL OF GRAPH THEORY, 2002, 39 (01) :62-75