Generalizations of the k-factor theorem

Abstract

In this paper, we give a more general sufficient condition for a degree sequence 〈di〉 to be realizable by a graph (without multiple edges and loops) containing a subgraph of specified degree sequence 〈ki〉. When sequences 〈di〉 and 〈di - ki〉 are both realizable by graphs, it was shown earlier that the condition k ≤ ki ≤ k + 1 for all i and some k ≥ 0 is sufficient for the existence of a 〈di〉-graph containing a 〈ki〉-subgraph. We now show that for k > 1 it is enough to assume, for example, that k ≤ ki ≤ k + 1 holds for all i except possibly i = i0, i1, where ki0 > 0 and ki1 > k + 1. © 1974.