K-regular factors and semi-k-regular factors in graphs Original Research Article

Let G be a graph, and let k ⩾ 1 be an integer. Let U be a subset of V(G), and let F be a spanning subgraph of G such that degF(x)=k for all x ∈ V(G) − U. If degF(x) ⩾ k for all x ∈ U, then F is called an upper semi-k-regular factor with defect set U, and if degF(x) ⩽ k for all x ∈ U, then F is called a lower semi-k-regular factor with defect set U. We show that if kvbV(G)vb is even, vbV(G)vb ⩾ k + 2, and for any subset U of cardinality k + 2 of V(G), G has an upper semi-k-regular factor with defect set U, then G has a k-factor. We also show that if k is even, vbV(G)vb ⩾ 2k + 4, and for any subset U of cardinality k + 3 of V(G), G has an upper semi-k-regular factor with defect set U, then G has a k-factor. Further, we show that if kvbV(G)vb is even, vbV(G)vb ⩾ k + 4, and for any subset U of cardinality 3 of V(G), G has a lower semi-k-regular factor with defect set U, then G has a k-factor.