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)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?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 |
|
|