A Neighborhood Condition for Graphs to Have [a,b] -Factors III

M. Kano and Haruhide Matsuda
Department of General Education, Kyushu Tokai University, Minami-Aso, Kumamoto 869-1404, Japan

Abstract

We consider finite undirected graphs without loops or multiple edges. Let G be a graph with vertex set V(G) and edge set E(G). We denote by |G| the order of G. For a vertex v of G, let deg_G (v) and N_G(v) denote the degree of v in G and the neighborhood of v in G, respectively. Furthermore, denotes the minimum degree of G, and N_G(S) = _{x S} N_G(x) for S V(G). Let a and b be integers such that 1 a b. An [a,b]-factor of G is a spanning subgraph F of G such that a deg_F(x) b for all x V(G). Note that an [a,a]-factor is a regular a-factor. We show a neighborhood condition for the existence of an [a,b]-factor which excludes some specified edges.

Main Theorem Let a, b, k, and m be positive integers such that 1 a < b and 2 k < (a+b+1-m)/a. Let G be a graph with |G|>(a+b)((k+m)(a+b-1)-1)/b. If

for every independent set {x₁,x₂, ... ,x_k} V(G), then for any subgraph H of G with m edges and (G-E(H))a, G has an [a,b]-factor F such that E(H) E(F)=.

The lower bound of the neighborhood condition is best possible in the sense that we cannot replace a|G|/(a+b) by a|G|/(a+b)-1.