Isolated Toughness and Fractional (g, f)-Factors of Graphs

被引:0
作者
Zhou, Sizhong [1 ]
Duan, Ziming [2 ]
Pu, Bingyuan [3 ]
机构
[1] Jiangsu Univ Sci & Technol, Sch Math & Phys, Zhenjiang 212003, Jiangsu, Peoples R China
[2] China Univ Min & Technol, Sch Sci, Xuzhou 221008, Jiangsu, Peoples R China
[3] Chengdu Text Coll, Dept Fundamental Educ, Chengdu 610023, Sichuan, Peoples R China
关键词
graph; isolated toughness; (g; f)-factor; fractional; SUFFICIENT CONDITIONS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph, and let a and b be nonnegative integers such that 1 <= a <= b, and let g and f be two nonnegative integer-valued functions defined on V(G) such that a <= g(x) <= f (x) <= b for each x is an element of V(G). A spanning subgraph F of G is called a fractional (g, f)-factor if g(x) <= d(G)(h)(x) <= f(x) for all x is an element of V(G), where d(G)(h)(x) = Sigma(e is an element of Ex) h(e) is the fractional degree of x is an element of V(F) with E-x = {e : e = xy is an element of E(G)}. The isolated toughness I(G) of a graph G is defined as follows: If G is a complete graph, then I(G) = +infinity; else, I(G) = min{vertical bar S vertical bar/i(G-S) : S subset of V(G), i(G - S) >= 2}, where i(G - S) denotes the number of isolated vertices in G - S. In this paper, we prove that G has a fractional (g, f)-factor if delta(G) >= I(G) >= b(b-1)/a+1. This result is best possible in some sense.
引用
收藏
页码:239 / 247
页数:9
相关论文
共 16 条
[1]   AN ALGORITHMIC PROOF OF TUTTES F-FACTOR THEOREM [J].
ANSTEE, RP .
JOURNAL OF ALGORITHMS, 1985, 6 (01) :112-131
[2]  
Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[3]   Sufficient conditions for graphs to have (g,f)-factors [J].
Egawa, Y ;
Kano, M .
DISCRETE MATHEMATICS, 1996, 151 (1-3) :87-90
[4]  
Jiang Jiashang, B AUSTR MAT IN PRESS
[5]   A SUFFICIENT CONDITION FOR A GRAPH TO HAVE [A,B]-FACTORS [J].
KANO, M .
GRAPHS AND COMBINATORICS, 1990, 6 (03) :245-251
[6]   TOUGHNESS OF GRAPHS AND THE EXISTENCE OF FACTORS [J].
KATERINIS, P .
DISCRETE MATHEMATICS, 1990, 80 (01) :81-92
[7]   Fractional (g, f)-factors of graphs [J].
Liu, GZ ;
Zhang, LJ .
ACTA MATHEMATICA SCIENTIA, 2001, 21 (04) :541-545
[8]  
Ma Yinghong, 2003, Acta Mathematicae Applicatae Sinica, V26, P133
[9]  
[MA Yinghong 马英红], 2006, [应用数学, Mathematics Applicata], V19, P188
[10]   Fan-type results for the existence of [a, b]-factors [J].
Matsuda, H .
DISCRETE MATHEMATICS, 2006, 306 (07) :688-693