Binding number, minimum degree and (g,f)-factors of graphs

  • Takamasa Yashima Keio University
Keywords: Graph Theory


Let a and b be integers with 2<= a< b, and let G be a graph of order n with n>= (a+b-1)^2/(a+1) and the minimum degree \delta(G)<= 1+(((b-2)n)/(a+b-1)).
Let g and f be nonnegative integer-valued functions defined on V(G) such that a<= g(x)<f(x)<= b for each x in V(G).

We prove that if the binding number bind(G)>=1+((b-2)/(a+1)), then G has a (g,f)-factor.


1. I. Anderson, Sufficient conditions for matching, Proc. Edinburgh Math. Soc. 18 (1973), 129-136.

2. C. Chen, Binding number and minimum degree for [a; b]-factors, J. Sys. Sci. and Math. Scis. 6 (1993), 179-185.

3. R. Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, 2010.

4. M. Kano and N. Tokushige, Binding numbers and f-factors of graphs, J. Combin. Theory Ser. B 54 (1992), 213-221.

5. L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970), 391-416.

6. N. Tokushige, Binding number and minimum degree for k-factors, J. Graph Theory 13 (1989), 607-617.

7. D. R. Woodall, The binding number of a graph and its Anderson number, J. Combin. Theory Ser. B 15 (1973), 225-255.