Annals of Combinatorics 2 (1998) 137-144
k-regular Factors and semi-k-regular Factors in Bipartite Graphs
Department of Applied Mathematics, Science University of Tokyo Shinjuku-ku, Tokyo 162-8601, Japan
Received April 22, 1998
AMS Subject Classification: 05C70
Let G be a graph, and k ≥ 1 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
Now let G=(X,Y; E(G)) be a bipartite graph with
bipartition (X,Y) such that |X|=|Y| ≥ k+2.
We prove the following two results.
Keywords: regular factor, semi-regular factor
1. A. Kaneko, private communication.
2. J. Folkman and D.R. Fulkerson, Flows in infinite graphs, J. Combin. Theory 8 (1970) 30–44.
3. Keiko Kotani, k-Regular Factors and Semi-k-Regular Factors in Graphs, Discrete Mathematics, 186 (1998) 177–193.