Binding number and Hamiltonian (g, f)-factors in graphs II

被引:1
|
作者
Cai, Jiansheng [2 ]
Liu, Guizhen [1 ]
Hou, Jianfeng [1 ]
机构
[1] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China
[2] Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
关键词
(g; f)-factor; Hamiltonian; binding number; computer science;
D O I
10.1080/00207160701524368
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N-G(X) = boolean OR(x is an element of X) N-G(x). The binding number of G is defined by bind(G) = min{vertical bar N-G(X)vertical bar/vertical bar X vertical bar vertical bar empty set not equal X subset of V(G), N-G(X) not equal V(G)}. Let G be a connected graph of order n, 3 <= a <= b be integers, and b >= 4. Let g, f be positive integer-valued functions defined on V(G), such that a <= g(x) <= f(x) <= b for every x is an element of V(G). Suppose n >= (a+b-4)(2)/(a-2) and f(V(G)) is even, we shall prove that if bind(G) > ((a+b-4)(n-1))/((a-2)n-(5/2)(a+b-4)) and for any independent set X subset of V(G), N-G(X) >= ((b-3)n + (2a+2b-9)vertical bar X vertical bar)/(a+b-5), then G has a Hamiltonian (g, f)-factor.
引用
收藏
页码:1325 / 1331
页数:7
相关论文
共 50 条