ON THE EXISTENCE OF GENERAL FACTORS IN REGULAR GRAPHS

摘要

Let G be a graph and H: V(G) → 2~N a set function associated with G. A spanning subgraph F of G is called an H-factor if the degree of any vertex v in F belongs to the set H(v). This paper contains two results on the existence of H-factors in regular graphs. First, we construct an r-regular graph without some given H*-factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lovasz's characterization theorem on the existence of (g,f)-factors, we find a sharp condition for the existence of general H-factors in {r, r + 1}-graphs in terms of the maximum and minimum of H. This result reduces to Thomassen's theorem for the case that H(v) consists of the same two consecutive integers for all vertices v and to Tutte's theorem if the graph is regular in addition.