Binding Number and Connected ( g, f+1)-factors in graphs

被引:0
作者
Cai, Jiansheng [1 ]
Liu, Guizhen [1 ]
Hou, Jianfeng [1 ]
机构
[1] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China
来源
COMPUTATIONAL SCIENCE - ICCS 2007, PT 3, PROCEEDINGS | 2007年 / 4489卷
关键词
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Let G be a connected graph of order n and let a, b be two integers such that 2 <= a <= b. Let g and f be two integer-valued functions defined on V(G) such that a <= g(x) <= f (x) <= b for every x is an element of V(G). A spanning subgraph F of G is called a (g, f + 1)-factor if g(x) <= d(F) (x) <= f (x) + 1 for every x is an element of V (F). For a subset X of V (G), let N-G (X) boolean OR N-G(x). The binding number of G is defined by bind(G) = min{N-G(X)(x is an element of X)vertical bar/vertical bar X vertical bar vertical bar theta not equal X subset of V(G), N-G (X) not equal V(G)}. In this paper, it is proved that if bind(G) >(a+b)(n-1)/an, f (V(G)) is even and n >= then (a+b)(2)/a, has a connected (g, f + 1)-factor.
引用
收藏
页码:313 / +
页数:2
相关论文
共 8 条
[1]  
Bondy A., 2008, GRAPH THEORY
[2]   BINDING NUMBERS AND F-FACTORS OF GRAPHS [J].
KANO, M ;
TOKUSHIGE, N .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 54 (02) :213-221
[3]   Connected factors in graphs - a survey [J].
Kouider, M ;
Vestergaard, PD .
GRAPHS AND COMBINATORICS, 2005, 21 (01) :1-26
[4]   On connected [g, f+1]-factors in graphs [J].
Li, GH ;
Xu, Y ;
Chen, CP ;
Liu, ZH .
COMBINATORICA, 2005, 25 (04) :393-405
[5]  
LOVASZ L., 1970, J. Combin. Theory, V8, P391, DOI [10.1016/S0021-9800(70)80033-3, DOI 10.1016/S0021-9800(70)80033-3]
[6]  
Plummer M., 2003, Handbook of Graph Theory, P403
[7]  
Woodall D. R., 1973, Journal of Combinatorial Theory, Series B, V15, P225, DOI 10.1016/0095-8956(73)90038-5
[8]  
[No title captured]