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
PDF
HTML XML
22
Downloads
105
Views
Citations

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

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.

Share and Cite:

Dai, W. , Liu, Y. and Wu, Y. (2024) Perfect 1-*k* Matchings of Bipartite Graphs. *Open Journal of Discrete Mathematics*, **14**, 43-53. doi: 10.4236/ojdm.2024.144005.

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*_{1} and *E*_{2} of $E\left(G\right)$
, the *symmetric* *difference* of *E*_{1} and *E*_{2} is denoted by ${E}_{1}\text{\hspace{0.17em}}\Delta \text{\hspace{0.17em}}{E}_{2}$
, that is, ${E}_{1}\text{\hspace{0.17em}}\Delta \text{\hspace{0.17em}}{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*_{4} 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.

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*_{1} be the subgraph induced by $Z\cup {N}_{G}\left(Z\right)$
. Then *H*_{1} satisfies the condition (1). By the induction hypothesis, *H*_{1} contains a 1-*k* matching, say *M*_{1}, which covers every vertex in *Z*. Let *H*_{2} be a subgraph induced by $\left(X-Z\right)\cup \left(Y-{N}_{G}\left(Z\right)\right)$
.

**Claim** **1** *H*_{2} 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*_{2}, say *M*_{2}, 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*_{0} 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*_{1} be the subgraph induced by ${S}_{0}\cup {N}_{G}\left({S}_{0}\right)$
and *H*_{2} 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*_{1} satisfies the condition (1). By the induction hypothesis, *H*_{1} has a 1-*k* matching *M*_{1} covering every vertex in *S*_{0}.

**Claim** **2** *H*_{2} 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*_{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|=\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*_{2} has a 1-*k* matching *M*_{2} 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*_{1} be the subgraph induced by ${S}_{0}\cup \left({N}_{G}\left({S}_{0}\right)-Z\right)$
and *H*_{2} the subgraph induced by $\left(X-{S}_{0}\right)\cup \left({T}_{2}\cup Z\right)$
.

**Claim** **3** *H*_{1} and *H*_{2} 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*_{1} satisfies the condition (1). Now we prove that *H*_{2} 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*_{1} has a 1-*k* matching *M*_{1} covering *S*_{0} and *H*_{2} has a 1-*k* matching *M*_{2} 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 $\sum}_{j=0}^{k}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{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* $\sum}_{j=0}^{k}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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*, $\sum}_{j=0}^{k}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{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}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{t}_{j}+{\displaystyle \sum}_{j=0}^{k}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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*_{1}. It is easy to check that *G*_{1} satisfies the condition (1) of the Theorem 2.1. Hence *G*_{1} has a 1-*k* matching, say *M*, which covers every vertex in *X*. Let *G*_{2} 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 $\sum}_{j=0}^{k}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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*_{0} 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*_{0}. 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*_{0}. 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*_{0} 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)\text{\hspace{0.17em}}\Delta \text{\hspace{0.17em}}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.

[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. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.