Perfect 1-k Matchings of Bipartite Graphs

Wenduan Dai, Yan Liu^*, Yanfang Wu

School of Mathematical Sciences, South China Normal University, Guangzhou, China.

DOI: 10.4236/ojdm.2024.144005                

Abstract

Let k be a positive integer and G a bipartite graph with bipartition $\left(X,Y\right)$ . A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering $\left|X\right|-d$ vertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

Keywords

Bipartite Graph, Semi-Matching, Perfect 1-k Matching, k-Elementary Graph

1. Introduction and Preliminaries

All graphs considered are simple, finite and undirected. Let G be a graph. The degree of a vertex v of G is denoted by $d_G\left(v\right)$ . The neighbour set of a vertex subset S of G is the set of vertices adjacent to a vertex in S, denoted by $N_G\left(S\right)$ . For two subsets E₁ and E₂ of $E\left(G\right)$ , the symmetric difference of E₁ and E₂ is denoted by $E_1\Delta E_2$ , that is, $E_1\Delta E_2=\left(E_1-E_2\right)\cup \left(E_2-E_1\right)$ . For two subsets $S,T$ of $V\left(G\right)$ , let $E_G\left(S,T\right)=\left\{uv\in E\left(G\right):u\in S,v\in T\right\}$ . The complete bipartite graph with bipartition $\left(X,Y\right)$ with that $\left|X\right|=s$ and $\left|Y\right|=t$ is denoted by $K_{s,t}$ . Specially, we denote by $K_{1,0}$ a single vertex. We refer to the book [1] for graph theoretical notations and terminology that are not defined here.

Let $G=\left(X,Y\right)$ be a bipartite graph with bipartition $\left(X,Y\right)$ . A semi-matching of G is defined as a set of edges $M\subseteq E\left(G\right)$ such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In general, valid semi-matchings of a connected graph G can be easily obtained by matching each vertex $y\in Y$ with an arbitrary vertex $x\in X$ for which $xy\in E\left(G\right)$ . In the computer science, the problem about the semi-matchings in a bipartite graph $G=\left(X,Y\right)$ is well known (see [2]), where Y corresponds to the clients (or tasks), X to the servers (or machines) and the number of edges in a semi-matching incident with a server (machine) in X is seen as the load on the server (machine). So semi-matchings are widely considered on different optimization objectives (see [3]-[6]). Many optimization objectives are to find the fairest semi-matching related to the load-balancing problem in a system, where a set of tasks need to be assigned to a set of machines in the fairest way. An example of the fairest semi-matching according to Jain’s index is shown in Figure 1 [5] and M₄ is the fairest one with the highest index of 0.86. Clearly, if $G=\left(X,Y\right)$ has a semi-matching M such that every vertex in X has the same load k, then M is a fairest semi-matching of G, which is said to be a perfect 1-k matching. Therefore, It is significant to study the new problem about 1-k matchings of a bipartite graph.

Figure 1. Semi-matching.

Now we give the definition of 1-k matchings. Let k be a positive integer. A 1-k matching with respect to X is an edge subset M of G such that each vertex in Y is incident with at most one edge in M and each vertex in X either is incident with exactly k edges in M or is not incident with any edge in M. In the following, 1-k matchings refer to ones with respect to X. A vertex is called M-saturated if it is incident with an edge in M, otherwise, it is M-unsaturated. A 1-k matching M is perfect if every vertex is M-saturated, that is, M covers every vertex of G. Then a perfect 1-k matching is an ideal state of semi-matchings which optimize some objectives.

When $k=1$ , a 1-k matching is a matching. When $k=2$ , Izumi and Watanabe [7] studied maximum 1 - 2 matching by giving augmenting trail, where augmenting trail is a generalization of the augmenting path for matchings and presented an algorithm for finding a maximum 1 - 2 matching in bipartite graphs.

Our work is to extend the matching theory on bipartite graphs to 1-k matching, motivated by the classical matching problem. Hall’s theorem is well known for judging the existence of perfect matchings [8] (see Theorem 1.1) and the deficient form of Hall’s theorem is given in [9] (see Corollary 1.1). Moreover, in the matching theory [8], the elementary bipartite graphs about matching are well characterized (see Proposition 1.1). An edge of a graph G is allowed if it lies in some perfect matching of G, otherwise, it is forbidden. A graph G is said to be elementary if its allowed edges form a connected spanning subgraph of G, that is, the subgraph obtained from G by deleting all forbidden edges is connected.

Theorem 1.1. (Hall’s Theorem [8]) A bipartite graph $G=\left(X,Y\right)$ has a matching which covers every vertex in X if and only if

$\left|N_G\left(S\right)\right|\ge \left|S\right|$

for any $S\subseteq X$ .

Corollary 1.1. [9] A bipartite graph $G=\left(X,Y\right)$ has a matching which covers $\left|X\right|-d$ vertices in X if and only if

$\left|N_G\left(S\right)\right|\ge \left|S\right|-d$

for any $S\subseteq X$ .

Proposition 1.1. [8] Let G be a bipartite graph with bipartition $\left(X,Y\right)$ . Then the following statements are equivalent:

1) G is elementary;

2) G has exactly two minimum vertex covers, named X and Y;

3) $\left|X\right|=\left|Y\right|$ and for every non-empty proper subset S of X, $\left|N_G\left(S\right)\right|\ge \left|S\right|+1$ ;

4) $G=K_2$ , or $\left|V\left(G\right)\right|\ge 4$ and for any $u\in X$ and $v\in Y$ , $G-u-v$ has a perfect matching;

5) G is connected and every edge of G is allowed.

In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering $\left|X\right|-d$ vertices in X, respectively. Moreover, we characterize k-elementary bipartite graph, which is a connected graph such that the subgraph induced by all k-allowed edges is connected.

2. Perfect 1-k Matching

We give the following theorem about 1-k matching similar to Hall’s theorem.

Theorem 2.1. A bipartite graph $G=\left(X,Y\right)$ has a 1-k matching, which covers every vertex in X if and only if

$\left|N_G\left(S\right)\right|\ge k\left|S\right|$ for any $S\subseteq X$ .(1)

Proof. It is obvious that if there exists a 1-k matching covering X, then the condition (1) holds. Now we prove “sufficiency” by induction on $\left|X\right|$ . Suppose that $\left|N_G\left(S\right)\right|\ge k\left|S\right|$ for any $S\subseteq X$ . When $\left|X\right|=1$ , we have that $\left|N_G\left(X\right)\right|\ge k$ . Then G has a 1-k matching covering X. Suppose that $\left|X\right|\ge 2$ . We consider the following three cases.

Case 1 There exists a non-empty proper subset Z of X such that $\left|N_G\left(Z\right)\right|=k\left|Z\right|$ .

Let H₁ be the subgraph induced by $Z\cup N_G\left(Z\right)$ . Then H₁ satisfies the condition (1). By the induction hypothesis, H₁ contains a 1-k matching, say M₁, which covers every vertex in Z. Let H₂ be a subgraph induced by $\left(X-Z\right)\cup \left(Y-N_G\left(Z\right)\right)$ .

Claim 1 H₂ satisfies the condition (1).

Suppose, to the contrary, that there exists $S\subseteq X-Z$ such that $\left|N_{H_2}\left(S\right)\right|<k\left|S\right|$ . Then

$\left|N_G\left(S\cup Z\right)\right|=\left|N_G\left(Z\right)\right|+\left|N_{H_2}\left(S\right)\right|<k\left|Z\right|+k\left|S\right|=k\left|Z\cup S\right|$ ,

which contradicts with the condition (1).

By Claim 1 and the induction hypothesis, there exists a 1-k matching of H₂, say M₂, which covers every vertex in $X-Z$ . Then $M_1\cup M_2$ is a 1-k matching of G covering every vertex in X.

Case 2 For any non-empty proper subset S of X, $\left|N_G\left(S\right)\right|\ge k\left|S\right|+1$ .

We choose a non-empty proper subset S₀ of X such that $\left|N_G\left(S_0\right)\right|-k\left|S_0\right|$ is smallest. Let $j=\left|N_G\left(S_0\right)\right|-k\left|S_0\right|$ . Then $j\ge 1$ and for any non-empty proper subset S of X, we have that $\left|N_G\left(S\right)\right|\ge k\left|S\right|+j$ . It is clear that $N_G\left(S_0\right)\subseteq N_G\left(X\right)$ and $N_G\left(X\right)-N_G\left(S_0\right)\subseteq N_G\left(X-S_0\right)$ . By the condition (1), $\left|N_G\left(X\right)\right|\ge k\left|X\right|$ . Then

$\left|N_G\left(X\right)-N_G\left(S_0\right)\right|=\left|N_G\left(X\right)\right|-\left|N_G\left(S_0\right)\right|\ge k\left|X-S_0\right|-j$ (2)

Subcase 1 $\left|N_G\left(X\right)-N_G\left(S_0\right)\right|\ge k\left|X-S_0\right|$ .

Let H₁ be the subgraph induced by $S_0\cup N_G\left(S_0\right)$ and H₂ the subgraph induced by $\left(X-S_0\right)\cup \left(N_G\left(X\right)-N_G\left(S_0\right)\right)$ . It is clear that H₁ satisfies the condition (1). By the induction hypothesis, H₁ has a 1-k matching M₁ covering every vertex in S₀.

Claim 2 H₂ satisfies the condition (1).

Clearly, $N_{H_2}\left(X-S_0\right)\subseteq N_G\left(X\right)-N_G\left(S_0\right)$ . Let $y\in N_G\left(X\right)-N_G\left(S_0\right)$ . Then there exists a vertex $x\in X-S_0$ such that $xy\in E\left(G\right)$ . Then $xy\in E\left(H_2\right)$ . Hence $y\in N_{H_2}\left(X-S_0\right)$ . Thus $N_G\left(X\right)-N_G\left(S_0\right)=N_{H_2}\left(X-S_0\right)$ . So we have that

$\left|N_{H_2}\left(X-S_0\right)\right|=\left|N_G\left(X\right)-N_G\left(S_0\right)\right|\ge k\left|X-S_0\right|.$

Suppose, to the contrary, that there exists a non-empty proper subset S₁ of $X-S_0$ such that $\left|N_{H_2}\left(S_1\right)\right|<k\left|S_1\right|$ . Let $S=S_0\cup S_1$ . Then

$\left|N_G\left(S\right)\right|=\left|N_G\left(S_0\right)\right|+\left|N_{H_2}\left(S_1\right)\right|<k\left|S_0\right|+j+k\left|S_1\right|=k\left|S\right|+j,$

which contradicts with that j is smallest.

By Claim 2 and the induction hypothesis, H₂ has a 1-k matching M₂ covering every vertex in $X-S_0$ . Hence $M_1\cup M_2$ is a 1-k matching of G covering every vertex in X.

Subcase 2 $\left|N_G\left(X\right)-N_G\left(S_0\right)\right|<k\left|X-S_0\right|$ .

Let $T_1=N_G\left(X-S_0\right)\cap N_G\left(S_0\right)$ and $T_2=N_G\left(X-S_0\right)-T_1$ . Then $T_2=N_G\left(X\right)-N_G\left(S_0\right)$ . According to (2) and the condition in the case, we have that

$k\left|X-S_0\right|-j\le \left|T_2\right|<k\left|X-S_0\right|.$

Thus $1\le k\left|X-S_0\right|-\left|T_2\right|\le j$ . Since

$\left|T_1\right|+\left|T_2\right|=\left|N_G\left(X-S_0\right)\right|\ge k\left|X-S_0\right|+j>\left|T_2\right|+j,$

we have that $\left|T_1\right|\ge j+1$ . Then we can choose a set $Z\subseteq T_1$ such that $\left|Z\right|=k\left|X-S_0\right|-\left|T_2\right|$ . Hence $1\le \left|Z\right|\le j$ . Let H₁ be the subgraph induced by $S_0\cup \left(N_G\left(S_0\right)-Z\right)$ and H₂ the subgraph induced by $\left(X-S_0\right)\cup \left(T_2\cup Z\right)$ .

Claim 3 H₁ and H₂ satisfy the condition (1).

Let $\varnothing \ne S^{\prime }\subseteq S_0$ . Then

$\left|N_{H_1}\left(S^{\prime }\right)\right|\ge \left|N_G\left(S^{\prime }\right)\right|-\left|Z\right|\ge k\left|S^{\prime }\right|+j-\left|Z\right|\ge k\left|S^{\prime }\right|.$

Hence H₁ satisfies the condition (1). Now we prove that H₂ also satisfies the condition (1). Clearly, $\left|N_{H_2}\left(X-S_0\right)\right|=\left|N_G\left(X\right)-N_G\left(S_0\right)\right|+\left|Z\right|=\left|T_2\right|+\left|Z\right|=k\left|X-S_0\right|$ . Suppose, to the contrary, that there exists a non-empty proper subset $S_1$ of $X-S_0$ such that $\left|N_{H_2}\left(S_1\right)\right|<k\left|S_1\right|$ . Let $S=S_0\cup S_1$ . Then

$\left|N_G\left(S\right)\right|\le \left|N_G\left(S_0\right)\right|+\left|N_{H_2}\left(S_1\right)\right|<k\left|S_0\right|+j+k\left|S_1\right|=k\left|S\right|+j,$

which contradicts with that j is smallest.

Hence by Claim 3 and the induction hypothesis, H₁ has a 1-k matching M₁ covering S₀ and H₂ has a 1-k matching M₂ covering every vertex in $X-S_0$ . Hence $M_1\cup M_2$ is a 1-k matching of G covering every vertex in X.

A bipartite graph $G=\left(X,Y\right)$ is called k-balanced with respect to X if $\left|Y\right|=k\left|X\right|$ . Now, we give the sufficiency and necessary conditions for the existence of perfect 1-k matchings.

Theorem 2.2. Let $G=\left(X,Y\right)$ be a k-balanced (with respect to X) bipartite graph. Then the following statements are equivalent:

1) G has a perfect 1-k matching;

2) $\left|N_G\left(S\right)\right|\ge k\left|S\right|$ for any $S\subseteq X$ ;

3) $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left|T\right|$ for any $T\subseteq Y$ ;

4) $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left|T\right|$ for any $T\subseteq Y$ such that $\left|T\right|\equiv 1\left(\mathrm{mod}k\right)$ .

Proof. “(1) $\iff$ (2)”. By Theorem 2.1, it is obvious.

“(2) $\Rightarrow$ (3)”. Let T be a subset of Y. If $T=\varnothing$ , then $\left|N_G\left(T\right)\right|=0=\frac{1}{k}\left|T\right|$ . Suppose that $T\ne \varnothing$ . Let $S=X-N_G\left(T\right)$ . Then

$k\left|X\right|-k\left|N_G\left(T\right)\right|=k\left|S\right|\le \left|N_G\left(S\right)\right|\le \left|Y\right|-\left|T\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left|T\right|$ .

“(3) $\Rightarrow$ (2)”. Let S be a subset of X. If $S=\varnothing$ , then $\left|N_G\left(S\right)\right|=0=k\left|S\right|$ . Suppose that $S\ne \varnothing$ . Let $T=Y-N_G\left(S\right)$ . Then

$\frac{1}{k}\left|Y\right|-\frac{1}{k}\left|N_G\left(S\right)\right|=\frac{1}{k}\left|T\right|\le \left|N_G\left(T\right)\right|\le \left|X\right|-\left|S\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(S\right)\right|\ge k\left|S\right|$ .

“(3) $\Rightarrow$ (4)”. It is obvious.

“(4) $\Rightarrow$ (3)”. Let T be a subset of Y. If $T=\varnothing$ , then $\left|N_G\left(T\right)\right|=0=\frac{1}{k}\left|T\right|$ .

Suppose $T\ne \varnothing$ . Let $\left|T\right|=km+c$ , where $m\ge 0$ and $0\le c\le k-1$ . We distinguish the following cases.

Case 1 $c=0$ .

Then $m\ge 1$ . Hence we can choose a subset $Z\subseteq T$ such that $\left|Z\right|=k\left(m-1\right)+1$ . Then $\left|Z\right|\equiv 1\left(\mathrm{mod}k\right)$ . Hence

$\left|N_G\left(T\right)\right|\ge \left|N_G\left(Z\right)\right|\ge \frac{1}{k}\left|Z\right|=\frac{1}{k}\left(km-k+1\right).$

Thus $\left|N_G\left(T\right)\right|\ge m=\frac{1}{k}\left|T\right|$ .

Case 2 $c\ne 0$ .

Without loss of generality, suppose that $2\le c\le k-1$ . Then we can choose a set $Z\subseteq T$ such that $\left|Z\right|=km+1$ . Hence

$\left|N_G\left(T\right)\right|\ge \left|N_G\left(Z\right)\right|\ge \frac{1}{k}\left|Z\right|=\frac{1}{k}\left(km+1\right).$

Thus $\left|N_G\left(T\right)\right|\ge m+1>\frac{1}{k}\left|T\right|$ .

In the following, we consider the deficient form of Theorem 2.2, similar to the deficient form of Hall’s theorem. If every component of a graph is $K_{s,t}$ and the number of components is m, then the graph is denoted by $m\cdot K_{s,t}$ . Let $G=\left(X,Y\right)$ be a bipartite graph and $\mathscr{H}=\left\{K_{1,j}:0\le j\le k\right\}$ . An $\mathscr{H}$ -quasi factor with respect to X of G is a subgraph H of G such that $V\left(H\right)\cap X=X$ and every component of H is isomorphic to a member $K_{1,j}$ in $\mathscr{H}$ such that the vertex

with degree j in $K_{1,j}$ is in X. Then we can assume that $H={\displaystyle \underset{0\le j\le k}{\cup }{t}_j\cdot K_{1,j}}$ , where $t_j\ge 0$ . Thus ${\displaystyle \sum }_{j=0}^k{t}_j=\left|X\right|$ .

Corollary 2.1. Let $G=\left(X,Y\right)$ be a k-balanced (with respect to X) bipartite graph. Then the following statements are equivalent:

1) G has an $\mathscr{H}$ -quasi factor $H={\displaystyle \underset{0\le j\le k}{\cup }{t}_j\cdot K_{1,j}}$ with respect to X such that $t_k\ge \left|X\right|-d$ and ${\displaystyle \sum }_{j=0}^{k}j{t}_j\ge \left|Y\right|-d$ , which implies that G has a 1-k matching covering at least $\left|X\right|-d$ vertices in X;

2) $\left|N_G\left(S\right)\right|\ge k\left|S\right|-d$ for any $S\subseteq X$ ;

3) $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left(\left|T\right|-d\right)$ for any $T\subseteq Y$ ;

4) $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left(\left|T\right|-d\right)$ for any $T\subseteq Y$ such that $\left|T\right|\equiv d+1\left(\mathrm{mod}k\right)$ .

Proof. “(1) $\Rightarrow$ (2)”. According to the definition of H, ${\displaystyle \sum }_{j=0}^k{t}_j=\left|X\right|$ . For any $S\subseteq X$ , let $S=S_0\cup S_1\cup \cdots \cup S_k$ , where $S_j\subseteq V\left[t_j\cdot K_{1,j}\right]$ . Then $\left|S_j\right|\le t_j$ . Hence we have that

$\begin{array}{c}\left|N_G\left(S\right)\right|\ge \left|N_H\left(S\right)\right|={\displaystyle \sum }_{i=0}^{k}j\left|S_j\right|={\displaystyle \sum }_{i=0}^k\left(k-\left(k-j\right)\right)\left|S_j\right|\\ =k\left|S\right|-{\displaystyle \sum }_{i=0}^k\left(k-j\right)\left|S_j\right|\ge k\left|S\right|-{\displaystyle \sum }_{i=0}^k\left(k-j\right)t_j\\ =k\left|S\right|-k{\displaystyle \sum }_{j=0}^k{t}_j+{\displaystyle \sum }_{j=0}^{k}j{t}_j\\ \ge k\left|S\right|-k\left|X\right|+\left|Y\right|-d=k\left|S\right|-d.\end{array}$

“(2) $\Rightarrow$ (1)”. Adding d new vertices $y_1,\cdots ,y_d$ to Y of G and joining them to each vertex in X, the resulting graph is denoted by G₁. It is easy to check that G₁ satisfies the condition (1) of the Theorem 2.1. Hence G₁ has a 1-k matching, say M, which covers every vertex in X. Let G₂ be the subgraph induced by M. Then $G_2=\left|X\right|\cdot K_{1,k}$ . Let $H=G_2-\left\{y_1,\cdots ,y_d\right\}$ . Then H is an $\mathscr{H}$ -quasi factor with respect to X of G, H has at least $\left|X\right|-d$ components which are $K_{1,k}$ ,

$V\left(H\right)\cap X=X$ and $\left|V\left(H\right)\cap Y\right|\ge k\left|X\right|-d=\left|Y\right|-d$ . Hence we can assume that

$H={\displaystyle \underset{j=0}{\overset{k}{\cup }}{t}_j\cdot K_{1,j}}$ and ${\displaystyle \sum }_{j=0}^{k}j{t}_j=\left|V\left(H\right)\cap Y\right|\ge \left|Y\right|-d$ and $t_k\ge \left|X\right|-d$ .

“(2) $\Rightarrow$ (3)”. Let T be a subset of Y. If $T=\varnothing$ , then $\left|N_G\left(T\right)\right|\ge 0\ge \frac{1}{k}\left(\left|T\right|-d\right)$ . Suppose that $T\ne \varnothing$ . Let $S=X-N_G\left(T\right)$ . Then

$k\left|X\right|-k\left|N_G\left(T\right)\right|-d=k\left|S\right|-d\le \left|N_G\left(S\right)\right|\le \left|Y\right|-\left|T\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(T\right)\right|\ge \frac{1}{k}\left(\left|T\right|-d\right)$ .

“(3) $\Rightarrow$ (2)”. Let S be a subset of X. If $S=\varnothing$ , then $\left|N_G\left(S\right)\right|\ge 0\ge k\left|S\right|$ . Suppose that $S\ne \varnothing$ . Let $T=Y-N_G\left(S\right)$ . Then

$\frac{1}{k}\left(\left|Y\right|-\left|N_G\left(S\right)\right|-d\right)=\frac{1}{k}\left(\left|T\right|-d\right)\le \left|N_G\left(T\right)\right|\le \left|X\right|-\left|S\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(S\right)\right|\ge k\left|S\right|-d$ .

“(3) $\Rightarrow$ (4)”. It is obvious.

“(4) $\Rightarrow$ (3)”. Let T be a subset of Y. If $\left|T\right|\le d$ , then $\left|N_G\left(T\right)\right|\ge 0\ge \frac{1}{k}\left(\left|T\right|-d\right)$ . Suppose that $\left|T\right|>d$ . Let $\left|T\right|-d=km+c$ , where $m\ge 0$ and $0\le c\le k-1$ . We distinguish the following cases.

Case 1 $c=0$ .

Then $m\ge 1$ . Hence we can choose a subset $Z\subseteq T$ such that $\left|Z\right|-d=k\left(m-1\right)+1$ . Hence

$\left|N_G\left(T\right)\right|\ge \left|N_G\left(Z\right)\right|\ge \frac{1}{k}\left(\left|Z\right|-d\right)=\frac{1}{k}\left(km-k+1\right).$

Thus $\left|N_G\left(T\right)\right|\ge m=\frac{1}{k}\left(\left|T\right|-d\right)$ .

Case 2 $c\ne 0$ .

Without loss of generality, suppose that $2\le c\le k-1$ . Then we can choose a set $Z\subseteq T$ such that $\left|Z\right|-d=km+1$ . Hence

$\left|N_G\left(T\right)\right|\ge \left|N_G\left(Z\right)\right|\ge \frac{1}{k}\left(\left|Z\right|-d\right)=\frac{1}{k}\left(km+1\right).$

Thus $\left|N_G\left(T\right)\right|\ge m+1>\frac{1}{k}\left(km+c\right)=\frac{1}{k}\left(\left|T\right|-d\right)$ .

3. Elementary Bipartite Graph about 1-k Matching

A edge of a graph G is k-allowed if it lies in some perfect 1-k matching of G, otherwise, it is k-forbidden. A bipartite graph is said to be a k-elementary graph if its k-allowed edges form a connected spanning subgraph of G. Now we characterize k-elementary bipartite graphs.

Theorem 3.1. Let $G=\left(X,Y\right)$ be a bipartite graph. Then the following statements are equivalent:

1) G is k-elementary;

2) G is connected, k-balanced (with respect to X) and $\left|N_G\left(S\right)\right|>k\left|S\right|$ for every non-empty proper subset S of X;

3) G is connected, k-balanced (with respect to X) and $\left|N_G\left(T\right)\right|>\frac{1}{k}\left|T\right|$ for every non-empty proper subset T of Y;

4) G is connected, k-balanced (with respect to X) and $\left|N_G\left(T\right)\right|>\frac{1}{k}\left|T\right|$ for every non-empty proper subset T of Y such that $\left|T\right|\equiv 0,1\left(\mathrm{mod}k\right)$ ;

5) G is connected and every edge of G is k-allowed;

6) $G=K_{1,k}$ , or $\left|V\left(G\right)\right|\ge 2k+2$ and for any $x\in X$ and $y\in Y$ , there exist $y_1,y_2,\cdots ,y_{k-1}\in N_G\left(x\right)-\left\{y\right\}$ such that $G-\left\{x,y,y_1,y_2,\cdots ,y_{k-1}\right\}$ has a perfect 1-k matching.

Proof. “(1) $\Rightarrow$ (2)”. Since G is k-elementary, then G is connected and has a perfect 1-k matching. Then $\left|Y\right|=k\left|X\right|$ and by Theorem 2.1, $\left|N_G\left(S\right)\right|\ge k\left|S\right|$ for any $S\subseteq X$ . Then G is k-balanced with respect to X. Suppose, to the contrary, that there exists a non-empty proper subset S₀ of X such that $\left|N\left(S_0\right)\right|=k\left|S_0\right|$ . Since G is k-elementary, there exists a k-allowed edge of G, say uv, such that $u\in X-S_0$ and $v\in N_G\left(S_0\right)$ . Hence we can assume that there exists a perfect 1-k matching M of G containing uv. Let H be the subgraph of G induced by $S_0\cup \left(N_G\left(S_0\right)-\left\{v\right\}\right)$ . Then $M\cap E\left(H\right)$ is a 1-k matching of H covering every vertex in S₀. But $\left|N_H\left(S_0\right)\right|=k\left|S_0\right|-1$ , which contradicts with Theorem 2.1.

“(2) $\Rightarrow$ (3)”. Let T be a non-empty proper subset of Y and $S=X-N_G\left(T\right)$ . If $N_G\left(T\right)=X$ , then $\left|N_G\left(T\right)\right|=\left|X\right|=\frac{1}{k}\left|Y\right|>\frac{1}{k}\left|T\right|$ . Suppose that $N_G\left(T\right)\subset X$ . Since G is connected, $N_G\left(T\right)\ne \varnothing$ . Then $S\ne \varnothing$ and $S\subset X$ . Hence

$k\left|X\right|-k\left|N_G\left(T\right)\right|=k\left|S\right|<\left|N_G\left(S\right)\right|\le \left|Y\right|-\left|T\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(T\right)\right|>\frac{1}{k}\left|T\right|$ .

“(3) $\Rightarrow$ (2)”. Let S be a non-empty proper subset of X and $T=Y-N_G\left(S\right)$ . If $N_G\left(S\right)=Y$ , then $\left|N_G\left(S\right)\right|=\left|Y\right|=k\left|X\right|>k\left|S\right|$ . Suppose that $N_G\left(S\right)\subset Y$ . Since G is connected, $N_G\left(S\right)\ne \varnothing$ . Then $T\ne \varnothing$ and $T\subset Y$ . Hence

$\frac{1}{k}\left|Y\right|-\frac{1}{k}\left|N_G\left(S\right)\right|=\frac{1}{k}\left|T\right|<\left|N_G\left(T\right)\right|\le \left|X\right|-\left|S\right|.$

Since $\left|Y\right|=k\left|X\right|$ , we have that $\left|N_G\left(S\right)\right|>k\left|S\right|$ .

“(3) $\Rightarrow$ (4)”. It is obvious.

“(4) $\Rightarrow$ (3)”. Let T be a non-empty proper subset of Y and $\left|T\right|=km+c$ , where $m\ge 0$ and $0\le c\le k-1$ . Without loss of generality, suppose that $2\le c\le k-1$ . Then we can choose a set $Z\subseteq T$ such that $\left|Z\right|=km+1$ . Hence

$\left|N_G\left(T\right)\right|\ge \left|N_G\left(Z\right)\right|>\frac{1}{k}\left|Z\right|=\frac{1}{k}\left(km+1\right).$

Thus $\left|N_G\left(T\right)\right|\ge m+1>\frac{1}{k}\left|T\right|$ .

“(2) $\Rightarrow$ (5)”. We prove that every edge is k-allowed. Let $v\in Y$ , $uv\in E\left(G\right)$ and $G_0=G-E_G\left(\left\{v\right\},X-\left\{u\right\}\right)$ . Then $d_{G_0}\left(v\right)=1$ . According to the condition (2), $d_G\left(x\right)\ge k+1$ for any $x\in X$ . Since G is connected, $N_{G_0}\left(X\right)=N_G\left(X\right)=Y$ . Since G is k-balanced, $\left|N_{G_0}\left(X\right)\right|=\left|Y\right|=k\left|X\right|$ . Suppose, to the contrary, that there exists a non-empty proper subset S of X such that $\left|N_{G_0}\left(S\right)\right|\le k\left|S\right|-1$ . Then

$\left|N_G\left(S\right)\right|\le \left|N_{G_0}\left(S\right)\right|+1\le k\left|S\right|-1+1=k\left|S\right|,$

a contradiction. By Theorem 2.2, there exists a perfect 1-k matching M of G₀. Then $uv\in M$ . Clearly, M is a perfect 1-k matching M of G. So every edge of G is k-allowed.

“(5) $\Rightarrow$ (1)”. It is obvious.

“(6) $\Rightarrow$ (2)”. It implies that G is k-balanced with respect to X and has a perfect 1-k matching. First, we prove that G is connected. Suppose, to the contrary, that G is disconnected. Let $G_1=\left(X_1,Y_2\right),\cdots ,G_s=\left(X_s,Y_s\right)$ be all components of G. Then every $G_i$ has a perfect 1-k matching. Hence $\left|Y_i\right|=k\left|X_i\right|$ for any $1\le i\le s$ . Let $x\in X_1$ and $y\in Y_2$ . It is clear that for any $y_1,\cdots ,y_{k-1}\in N_G\left(x\right)-\left\{y\right\}$ , $G-\left\{x,y,y_1,\cdots ,y_{k-1}\right\}$ has no perfect 1-k matchings, a contradiction. So G is connected. Secondly, we prove that $\left|N_G\left(S\right)\right|>k\left|S\right|$ for every non-empty proper subset S of X. By Theorem 2.2, $\left|N_G\left(S\right)\right|\ge k\left|S\right|$ . Suppose, to the contrary, that there exists a non-empty proper subset S₀ of X such that $\left|N_G\left(S_0\right)\right|=k\left|S_0\right|$ . Let $x\in X-S_0$ and $y\in N_G\left(S_0\right)$ . Then there exist $y_1,\cdots ,y_{k-1}\in N_G\left(x\right)-\left\{y\right\}$ such that $G-\left\{x,y,y_1,\cdots ,y_{k-1}\right\}$ has a perfect 1-k matching. Let $H=G-\left\{x,y,y_1,\cdots ,y_{k-1}\right\}$ . Then

$\left|N_H\left(S_0\right)\right|\le k\left|S_0\right|-1,$

which contradicts with Theorem 2.2.

“(3) $\Rightarrow$ (6)”. Since G is connected and k-balanced with respect to X, we have that $\left|N_G\left(Y\right)\right|=\left|X\right|=\frac{1}{k}\left|Y\right|$ . By Theorem 2.2, G has a perfect 1-k matching, say M.

When $\left|X\right|=1$ , $G=K_{1,k}$ . Suppose that $\left|X\right|\ge 2$ . Let H be the subgraph induced by M. Let $x\in X$ and $y\in Y$ .

Case 1 $xy\in E\left(H\right)$

Let $y_1,\cdots ,y_{k-1}\in N_H\left(x\right)-\left\{y\right\}$ . Then $H-\left\{x,y,y_1,\cdots ,y_{k-1}\right\}$ has a perfect 1-k matching. Hence $G-\left\{x,y,y_1,\cdots ,y_{k-1}\right\}$ has a perfect 1-k matching.

Case 2 $xy\notin E\left(H\right)$

Let $X=\left\{x_1,\cdots ,x_m\right\}$ and $Y_i=N_H\left(x_i\right)=\left\{y_{i1},\cdots ,y_{ik}\right\},1\le i\le m$ . Then $\left|Y_i\right|=k$ . Let $G^{\text{*}}$ be the resulting graph obtained from G by shrinking every $Y_i$ to a single vertex $y_i^{\text{*}}$ and deleting the multiple edges. Then $G^{\text{*}}$ is a bipartite graph with bipartition $\left(X,\left\{y_1^{\text{*}},\cdots ,y_m^{\text{*}}\right\}\right)$ . Then $M^{\text{*}}=\left\{x_1{y}_1^{\text{*}},\cdots ,x_m{y}_m^{\text{*}}\right\}$ is a perfect matching

of $G^{\text{*}}$ . Since $\left|N_G\left(T\right)\right|>\frac{1}{k}\left|T\right|$ for any non-empty proper subset T of Y, we have that

$\left|N_{G^{\text{*}}}\left(T^{\text{*}}\right)\right|=\left|N_G\left({\displaystyle \underset{y_i^{\text{*}}\in T^{\text{*}}}{\cup }{Y}_i}\right)\right|>\frac{1}{k}\left|{\displaystyle \underset{y_i^{\text{*}}\in T^{\text{*}}}{\cup }{Y}_i}\right|=\left|T^{\text{*}}\right|$

for any non-empty proper subset $T^{\text{*}}$ of $Y^{\text{*}}$ . Without loss of generality, suppose that $x=x_1$ and $y=y_{mk}\in Y_m$ . By Proposition 1.1, $G^{\text{*}}-x_1-y_m^{\text{*}}$ has a perfect matching. Let $M_1^{\text{*}}=M^{\text{*}}-\left\{x_1{y}_1^{\text{*}},x_m{y}_m^{\text{*}}\right\}$ . Then $M_1^{\text{*}}$ is not a maximum matching of $G^{\text{*}}-x_1-y_m^{\text{*}}$ and $x_m$ , $y_1^{\text{*}}$ are $M_1^{\text{*}}$ -unsaturated vertices. So there exists an $M_1^{\text{*}}$ -augmenting path $P^{\text{*}}$ of $G^{\text{*}}-x_1-y_m^{\text{*}}$ joining $y_1^{\text{*}}$ and $x_m$ . Without loss of generality, suppose that $P^{\text{*}}=y_1^{\text{*}}{x}_2{y}_2^{\text{*}}{x}_3{y}_3^{\text{*}},\cdots ,x_q{y}_q^{\text{*}}{x}_m$ . Then we can assume that $P=y_{1k}{x}_2{y}_{2k}{x}_3{y}_{3k},\cdots ,x_q{y}_{qk}{x}_m$ is a path of $G-x_1-y_{mk}$ joining $y_{1k}$ and $x_m$ . Let $M^{\prime }=\left(M-\left\{x_1{y}_{11},\cdots ,x_1{y}_{1k},x_m{y}_{mk}\right\}\right)\Delta E\left(P\right)$ . Then $M^{\prime }$ is a perfect 1-k matching of $G-\left\{x,y,y_{11},y_{12},\cdots ,y_{1\left(k-1\right)}\right\}$ .

Supported

This work is supported by the National Natural Science Foundation of China (No.12161073).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer-Verlag, Berlin.
[2]	Lawler, E. (2001) Combinatorial Optimization: Networks and Matroids. Dover Publications, New York.
[3]	Harvey, N.J.A., Ladner, R.E., Lovász, L. and Tamir, T. (2006) Semi-Matchings for Bipartite Graphs and Load Balancing. Journal of Algorithms, 59, 53-78. https://doi.org/10.1016/j.jalgor.2005.01.003
[4]	Czygrinow, A., Hanćkowiak, M., Szymańska, E. and Wawrzyniak, W. (2016) On the Distributed Complexity of the Semi-Matching Problem. Journal of Computer and System Sciences, 82, 1251-1267. https://doi.org/10.1016/j.jcss.2016.05.001
[5]	Xu, J., Banerjee, S. and Rao, W. (2020) The Existence of Universally Agreed Fairest Semi-Matchings in Any Given Bipartite Graph. Theoretical Computer Science, 818, 83-91. https://doi.org/10.1016/j.tcs.2018.03.020
[6]	Low, C.P. (2006) An Approximation Algorithm for the Load-Balanced Semi-Matching Problem in Weighted Bipartite Graphs. Information Processing Letters, 100, 154-161. https://doi.org/10.1016/j.ipl.2006.06.004
[7]	Izumi, H., Watanabe, S. and Watanabe, Y. (2017) Augmenting Trail Theorem for the Maximum 1-2 Matching Problem. Discrete Mathematics, Algorithms and Applications, 9, 1750056. https://doi.org/10.1142/s1793830917500562
[8]	Lovasz, L. and Plummer, M. (1986) Matching Theory. North-Holland, New York
[9]	Bollobás, B. (1998) Modern Graph Theory. Springer, New York.