Annals of Combinatorics 2 (1998) 137-144


k-regular Factors and semi-k-regular Factors in Bipartite Graphs

Keiko Kotani

Department of Applied Mathematics, Science University of Tokyo Shinjuku-ku, Tokyo 162-8601, Japan
j1195701@ed.kagu.sut.ac.jp

Received April 22, 1998

AMS Subject Classification: 05C70

Abstract. 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 xV(G)-U. If degF(x) ≥ k for all xU, then F is called an upper semi-k-regular factor with defect set U, and if degF(x) ≤ k for all xU, then F is called a lower semi-k-regular factor with defect set U. 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.

  1. Suppose that for each subset U1 X such that |U1|=max{k+1, }, G has an upper semi-k-regular factor with defect setU1Y, and for each subset U2 Y such that |U2|= max{k+1, }, G has an upper semi-k-regular factor with defect set XU2. Then G has a k-factor.
  2. Suppose that for each subset U1 X such that |U1| = , G has a lower semi-k-regular factor with defect set U1Y, and for each subset U2 Ysuch that |U2| = , G has a lower semi-k-regular factor with defect set XU2. Then G has a k-factor.

Keywords: regular factor, semi-regular factor


References

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.


Get the LaTex | DVI | PS file of this abstract.

back