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

Abstract

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)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ∅≠X⊂V(G), N _G (X)≠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∈V(G). Suppose n≥(a+b−4)²/(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⊂V(G), N _G (X)≥((b−3)n+(2a+2b−9)| X|)/(a+b−5), then G has a Hamiltonian (g, f)-factor.

Keywords:

• (g, f)-factor
• Hamiltonian (g, f)-factor
• binding number
• computer science

2000 AMS Subject Classification :

• 05C70

Acknowledgements

This work was supported by the National Natural Science Foundation(10471078) and the Doctoral Program Foundation of Education Ministry (20040422004) of China.