# Bipartite Toughness andk-Factors in Bipartite Graphs

Authors: Guizhen Liu; Jianbo Qian; Jonathan Z. Sun; Rui Xu
Journal: International Journal of Mathematics and Mathematical Sciences
 (2008)

---

## Abstract

We define a new invarianttB(G) in bipartite graphs that is analogous to the
toughness t(G) and we give sufficient conditions in term of tB(G) for the existence of k-factors in bipartite graphs. We also show that these results are sharp.


---

## Body

## 1. Introduction

Toughness,
like connectivity, is an important invariant in graphs. There has been extensive work on toughness (see the survey in [1]) since Chvátal introduced
the concept in 1973 [2]. The toughness t(G) of a graph G is the minimum value of |S|/w(G−S),
where S⊂V(G) is a proper subset of the vertices of G and w(G−S)>1 is the number of connected components after
removing S from G.
(If G is a complete graph so that w(G−S) is always equal to 1, then t(G) is set to be ∞.)
That is, for any integer k>1, G cannot be split into k connected components by removing less than k⋅t(G) vertices. We also say that G is t(G)-tough. Chvátal made a number of conjectures
in [2], including the
famous 2-tough conjecture saying that every 2-tough graph has a Hamiltonian
cycle. Having inspired many interesting results, the 2-tough conjecture itself
was showed to be false by Bauer et al. in 2000 [3].A subgraphH of G is called a factor of G if H is a spanning subgraph of G.
An important class of factors is k-factors, also called regular degree
factors, where every vertex of G has degree k in H.
(Note that a perfect matching is a 1-factor, and a Hamiltonian cycle is a
connected 2-factor.) There has been extensive work on the conditions of
existence of various factors in graphs. Many results can be found in the latest
survey by Plummer [4].It is natural to expect that toughness, yet another
measure of the connectivity of a graph, ought to relate to the existence ofk-factors in graphs. Enomoto et al. [5–7] proved that every k-tough graph contains a k-factor if it satisfies trivial necessary
conditions, and there are (k−ε)-tough graphs for any ε>0 that do not contain a k-factor. Consider a bipartite graphG=(X,Y;E), where X∪Y=V(G) is a partition of V(G) and E is the edge set of G with each edge having one end in X and the other in Y. Katerinis [8] proved
that every 1-tough bipartite graph has a 2-factor. Recall that the toughness of
a bipartite graph G=(X,Y;E) is at most 1 because the removal of X from G (assuming |X|≥|Y|) results in an independent set Y.
Therefore, it is not possible to use toughness to predict the existence of k-factors in balanced bipartite graphs for any k≥3.


### 1.1. Bipartite Toughness

In this paper,
we introducebipartite toughness, which is analogous to the concept of
toughness but reflects the bipartition of V(G).
The bipartite toughness tB(G) of a bipartite graph G=(X,Y;E) is the minimum value of |S|/w(G−S),
where S is a proper subset of X or Y and w(G−S)>1 is the number of connected components after
removing S from G.
We set tB(G)=∞ for complete bipartite graphs, just like t(G)=∞ for complete graphs.A bipartite graph can have a regular degree factor
only if|X|=|Y|.
Therefore, in the rest of the paper, we consider only a balanced bipartite
graph with |X|=|Y|=n.
For a subset S of V(G),
we use N(S) to denote the set of vertices adjacent to at
least one vertex in S.
For two disjoint subsets S and T of V(G),
we use eG(S,T) to stand for the number of edges having one end
in S and the other in T.
Other terminologies and notations used in this paper follow [9] and other references.Bipartite toughnesstB(G) measures the connectivity of a bipartite graph
better than toughness t(G) does. In contrast to toughness t(G) that is at most 1 in a bipartite graph, tB(G) can be arbitrarily big. For example, in a complete bipartite graph with
one edge deleted, t(G)=O(n), which approaches to ∞,
is just like t(G)=O(n) in a complete graph with one edge deleted.
Interestingly, tB(G) a better invariant to predict the existence of k-factors in balanced bipartite graphs, for any k.
Furthermore, by their definitions, calculating tB(G) in a bipartite graph is easier than
calculating t(G) since one is a subtask of the other.


### 1.2. Our Results

LetG=(X,Y;E) be a balanced bipartite graph with |X|=|Y|=n and 1≤k≤n be an integer. In this paper, we prove the
following three theorems.Theorem 1.1.
Letm=⌊(n−1)/2⌋. If tB(G)>m/(m+2),
then G has a 1-factor.Theorem 1.2.
Fork≥2 and n≥4k−4,
if tB(G)>f1=(2k−1)(n−1)/(kn+1),
then G has a k-factor.Theorem 1.3.
Forn≤4k−4,
if tB(G)>f2=(n−1)/(2kn+1−2k+1),
then G has a k-factor.These theorems together give a sharp bound oftB(G) for G to have a k-factor, for k=1,…,n.
(See Figure 1. Note that m/(m−2)=f1 when k=1 and n is odd; and f1=f2 when n=4k−4.)Figure 1
The bound of bipartite toughness in Theorems1.2 and 1.3, illustrated with n=1000.
The x-axis is k and y-axis is log(tB(G)).
The bound is given by f1 on the left and f2 on the right of k=(n+4)/4.The bound oftB(G) is sharp in the following senses.(a)
For Theorem1.1, let m=⌊(n−1)/2⌋ and construct a balanced bipartite graph G=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q, where |P|=|T|=n−m, |S|=|Q|=m,
and |X|=|Y|=n.
Let E be comprised of all possible edges between X and Q and all possible edges between S and Y.
If n is even, then we add into E an edge between P and T.
Here, |S|+eG(X−S,T)−|T|=−1 so that by Lemma 2.1 below, G has no 1-factor. On the other hand, it is not
hard to verify that tB(G)=m/(m+2) in this construction of G.
Therefore, m/(m+2) is a sharp bound.(b)
For Theorem1.2, for integers k≥2 and r≥2,
construct a balanced bipartite graph Gr=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q,
where |P|=|T|=kr−1, |S|=|Q|=(k−1)r−1,
and |X|=|Y|=n=(2k−1)r−2≥4k−5.
Let E be comprised of all possible edges between X and Q,
all possible edges between S and Y,
and a 1-factor between P and T.
Here, k|S|+eG(X−S,T)−k|T|=−1 so that by Lemma 2.1 below, Gr has no k-factor. On the other hand, it is not hard to
verify that tB(Gr)=(n−1)/(n−|S|)=(2k−1)(n−1)/(kn+1)=f1 in Gr.
Therefore, f1 is a sharp bound.(c)
For Theorem1.3. Let n/4<k<n and kn+1=t be an integer. Obviously, n/2<t<n.
Construct a balanced bipartite graph G=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q, where |P|=|T|=t, |S|=|Q|=n−t,
and |X|=|Y|=n.
Let E be comprised of all possible edges between X and Q,
all possible edges between S and Y,
and a (2k−t)-factor between P and T.
Then k|S|+eG(X−S,T)−k|T|=k(n−t)+(2k−t)t−kt=kn−t2=−1.
Again, by Lemma 2.1 below, G has no k-factor. Moreover, it is not hard to verify
that tB(G)=(n−1)/(2kn+1−2k+1).
Therefore, f2 is also a sharp bound.It is also worth to mention that, unlike Enomoto et al.'s well-known result thatk-tough graphs have k-factors, in our results the bound of tB(G) is much smaller than k,
in fact less than 2 for most k (see Figure 1). This looks counterintuitive
but it is due to a (not so good) feature of tB(G).
Although tB(G) can approach to ∞,
most time it does not increase significantly with edge connectivity or minimum
degree. For example, if G=(X,Y;E), |X|=|Y|=n has minimum degree δ(G)=n/2 (say on vertex x∈X), then removing all vertices in X except x would split Y into n/2 components. So tB(G)≤2 even when δ(G) is as high as n/2.


## 1.1. Bipartite Toughness

In this paper,
we introducebipartite toughness, which is analogous to the concept of
toughness but reflects the bipartition of V(G).
The bipartite toughness tB(G) of a bipartite graph G=(X,Y;E) is the minimum value of |S|/w(G−S),
where S is a proper subset of X or Y and w(G−S)>1 is the number of connected components after
removing S from G.
We set tB(G)=∞ for complete bipartite graphs, just like t(G)=∞ for complete graphs.A bipartite graph can have a regular degree factor
only if|X|=|Y|.
Therefore, in the rest of the paper, we consider only a balanced bipartite
graph with |X|=|Y|=n.
For a subset S of V(G),
we use N(S) to denote the set of vertices adjacent to at
least one vertex in S.
For two disjoint subsets S and T of V(G),
we use eG(S,T) to stand for the number of edges having one end
in S and the other in T.
Other terminologies and notations used in this paper follow [9] and other references.Bipartite toughnesstB(G) measures the connectivity of a bipartite graph
better than toughness t(G) does. In contrast to toughness t(G) that is at most 1 in a bipartite graph, tB(G) can be arbitrarily big. For example, in a complete bipartite graph with
one edge deleted, t(G)=O(n), which approaches to ∞,
is just like t(G)=O(n) in a complete graph with one edge deleted.
Interestingly, tB(G) a better invariant to predict the existence of k-factors in balanced bipartite graphs, for any k.
Furthermore, by their definitions, calculating tB(G) in a bipartite graph is easier than
calculating t(G) since one is a subtask of the other.


## 1.2. Our Results

LetG=(X,Y;E) be a balanced bipartite graph with |X|=|Y|=n and 1≤k≤n be an integer. In this paper, we prove the
following three theorems.Theorem 1.1.
Letm=⌊(n−1)/2⌋. If tB(G)>m/(m+2),
then G has a 1-factor.Theorem 1.2.
Fork≥2 and n≥4k−4,
if tB(G)>f1=(2k−1)(n−1)/(kn+1),
then G has a k-factor.Theorem 1.3.
Forn≤4k−4,
if tB(G)>f2=(n−1)/(2kn+1−2k+1),
then G has a k-factor.These theorems together give a sharp bound oftB(G) for G to have a k-factor, for k=1,…,n.
(See Figure 1. Note that m/(m−2)=f1 when k=1 and n is odd; and f1=f2 when n=4k−4.)Figure 1
The bound of bipartite toughness in Theorems1.2 and 1.3, illustrated with n=1000.
The x-axis is k and y-axis is log(tB(G)).
The bound is given by f1 on the left and f2 on the right of k=(n+4)/4.The bound oftB(G) is sharp in the following senses.(a)
For Theorem1.1, let m=⌊(n−1)/2⌋ and construct a balanced bipartite graph G=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q, where |P|=|T|=n−m, |S|=|Q|=m,
and |X|=|Y|=n.
Let E be comprised of all possible edges between X and Q and all possible edges between S and Y.
If n is even, then we add into E an edge between P and T.
Here, |S|+eG(X−S,T)−|T|=−1 so that by Lemma 2.1 below, G has no 1-factor. On the other hand, it is not
hard to verify that tB(G)=m/(m+2) in this construction of G.
Therefore, m/(m+2) is a sharp bound.(b)
For Theorem1.2, for integers k≥2 and r≥2,
construct a balanced bipartite graph Gr=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q,
where |P|=|T|=kr−1, |S|=|Q|=(k−1)r−1,
and |X|=|Y|=n=(2k−1)r−2≥4k−5.
Let E be comprised of all possible edges between X and Q,
all possible edges between S and Y,
and a 1-factor between P and T.
Here, k|S|+eG(X−S,T)−k|T|=−1 so that by Lemma 2.1 below, Gr has no k-factor. On the other hand, it is not hard to
verify that tB(Gr)=(n−1)/(n−|S|)=(2k−1)(n−1)/(kn+1)=f1 in Gr.
Therefore, f1 is a sharp bound.(c)
For Theorem1.3. Let n/4<k<n and kn+1=t be an integer. Obviously, n/2<t<n.
Construct a balanced bipartite graph G=(X,Y;E) as follows. Let X=S∪P and Y=T∪Q, where |P|=|T|=t, |S|=|Q|=n−t,
and |X|=|Y|=n.
Let E be comprised of all possible edges between X and Q,
all possible edges between S and Y,
and a (2k−t)-factor between P and T.
Then k|S|+eG(X−S,T)−k|T|=k(n−t)+(2k−t)t−kt=kn−t2=−1.
Again, by Lemma 2.1 below, G has no k-factor. Moreover, it is not hard to verify
that tB(G)=(n−1)/(2kn+1−2k+1).
Therefore, f2 is also a sharp bound.It is also worth to mention that, unlike Enomoto et al.'s well-known result thatk-tough graphs have k-factors, in our results the bound of tB(G) is much smaller than k,
in fact less than 2 for most k (see Figure 1). This looks counterintuitive
but it is due to a (not so good) feature of tB(G).
Although tB(G) can approach to ∞,
most time it does not increase significantly with edge connectivity or minimum
degree. For example, if G=(X,Y;E), |X|=|Y|=n has minimum degree δ(G)=n/2 (say on vertex x∈X), then removing all vertices in X except x would split Y into n/2 components. So tB(G)≤2 even when δ(G) is as high as n/2.


## 2. Proofs of the Theorems

The following
lemma will be needed in the proofs of theorems.Lemma 2.1.
LetG=(X,Y;E) be a balanced bipartite graph, where |X|=|Y|=n,
and let k≥1 be an integer. Then the following three
statements are equivalent:
(i)
G has a k-factor;(ii)
G has k edge-disjoint 1-factors;(iii)
for anyS⊆X and T⊆Y, k|S|+eG(X−S,T)−k|T|≥0.Proof.
(i) and (ii): following the
König-Hall theorem [9, Theorem 5.2 and Lemma 5.2], a regular degree bipartite graph has a perfect
matching. Therefore, a k-factor of a bipartite graph G can be partitioned into a collection of k edge-disjoint perfect matchings (1-factors).
(ii) to (i) is trivial.
(i) and (iii): the equivalence of (i) and (iii) can be
deduced from the max-flow min-cut theorem [10, 11]. Convert G=(X,Y;E) into a network by (a) adding a source vertex s with k multiedges between s and each vertex x∈X;
(b) adding a sink vertex t with k multiedges between t and each vertex y∈Y;
and (c) orienting each edge into a directed arc going from s to X,
from X to Y,
or from Y to t (see Figure 2). Clearly, G has a k-factor ⇔ the network has a kn-flow from s to t⇔ any cut in the network that separates s and t contains at least kn forward edges. For any S⊆X and T⊆Y,
consider the cut shown in dashed line in Figure 2, we have(2.1)k|S|+eG(X−S,T)+k|Y−T|≥kn=k|T|+k|Y−T|,so that(2.2)k|S|+eG(X−S,T)−k|T|≥0.Figure 2
For proof of Lemma2.1, red dashed line is the minimum cut.Proof.
SupposeG has no k-factor and n≥4k−4,
we will infer that tB(G)≤f1.
According to Lemma 2.1, there exist S⊆X and T⊆Y such that k|S|+eG(X−S,T)−k|T|<0.
Let s=|S| and t=|T|.
Then(2.3)eG(X−S,T)≤kt−ks−1.Obviously, t>s.
We can further assume that(2.4)s+t≤n.Because, if s+t>n,
then we can let S′=X−S and T′=Y−T and have |S′|+|T′|<n, |S′|>|T′|,
and k|T′|+eG(S′,Y−T′)−k|S′|=k|S|+eG(X−S,T)−k|T|.
By symmetry, this converts to the case of s+t≤n.
We then have two cases to consider.Case 1.
(2.5)k(t−s)≤t.
Ifk=1,
then w(G−S)≥t+1−(t−s−1)=s+2 by (2.3). By t>s and (2.4), we have s≤m,
where m=⌊(n−1)/2⌋. Thus(2.6)tB(G)≤|S|w(G−S)≤ss+2≤mm+2.This completes the proof of
Theorem 1.1. (Note that when k=1,
we have only Case 1 to consider.)Proof.
Now supposek≥2,
by (2.5), we have t≤ks/(k−1).
Let T′=T∩N(X−S).
Then by (2.3), |T′|≤kt−ks−1.
Let T′′=(Y−T)∪T′.
Then |T′′|≤n−t+(kt−ks−1)<n and w(G−T′′)≥n−s+1.
Therefore,(2.7)tB(G)≤|T′′|w(G−T′′)≤n+(k−1)t−ks−1n−s+1.
Case 2.
Ifn−s≤ks/(k−1),
then we have s≥(k−1)n/(2k−1).
By (2.4) and (2.7),(2.8)tB(G)≤n+(k−1)(n−s)−ks−1n−s+1=2k−1−(k−1)n+2kn−s+1≤2k−1−(k−1)n+2kn−(k−1)n/(2k−1)+1=(2k−1)(n−1)kn+2k−1≤(2k−1)(n−1)kn+1=f1.
Case 2.
Ifn−s>ks/(k−1),
then we have s<(k−1)n/(2k−1).
By (2.5) and (2.7),(2.9)tB(G)≤n−1n−s+1<n−1n−(k−1)n/(2k−1)+1=(2k−1)(n−1)kn+2k−1≤(2k−1)(n−1)kn+1=f1.Case 2.
(2.10)k(t−s)>t.
Letd be the unique integer satisfying(2.11)t⋅d<k(t−s)≤(d+1)t.By (2.10), 1≤d≤k−1.
By (2.3) and (2.11), there is a vertex y0∈T that is adjacent to at most d vertices in X−S.
Let T′=Y−{y0} so |T′|=n−1 and w(G−T′)≥n−s−d+1.
By (2.4) and (2.11), we have s≤[(k−d)n−1]/(2k−d).
Therefore,(2.12)tB(G)≤n−1n−s−d+1≤n−1n−((k−d)n−1)/(2k−d)−d+1.Define a function g(d)=n−[(k−d)n−1]/(2k−d)−d+1.
It is easy to verify that, by the assumption of n≥4k−4, g(1)≤g(2).
Since g(d) is a convex function, it follows that f(1)≤f(d) for d>1.
By (2.12),(2.13)tB(G)≤n−1f(d)≤n−1f(1)=(2k−1)(n−1)(kn+1)=f1.
This completes the proof of
Theorem1.2.Proof.
Indeed, we will prove that the result in Theorem1.3
holds for all 1≤k≤n.
The condition of n≥4k−4 in Theorem 1.3 is only because that f2 is not as tight a bound as f1 when n<4k−4.
SupposeG has no k-factor, we will infer that tB(G)≤f2.
According to Lemma 2.1, there exist S⊆X and T⊆Y such that(2.14)eG(X−S,T)≤kt−ks−1,where s=|S| and t=|T|.
Like in the proof of Theorems 1.1 and 1.2, we can still assume (2.4).
Supposey0 is vertex in T that is adjacent to the least number (denoted
by d) of vertices in X−S.
By (2.14), we have t⋅d≤kt−ks−1.
Then with (2.4), we further have s≤[(k−d)n−1]/(2k−d).
Let T′=Y−{y0},
then |T′|=n−1 and w(G−T′)≥n−s−d+1.
Therefore,(2.15)tB(G)≤|T′|w(G−T′)≤n−1n−s−d+1≤n−1n−((k−d)n−1)/(2k−d)−d+1=n−1(2k−d)+(kn+1)/(2k−d)−2k+1≤n−12kn+1−2k+1=f2.
This completes
the proof of Theorem1.3.


## 3. Conclusion and Future Work

We have defined
a new invariant in bipartite graphs called bipartite toughness and provided a
sharp bound of it for a balanced bipartite graph to have ak-factor, for k from 1 through n.
We view this as a big improvement from using toughness to predict k-factors in bipartite graphs, as toughness of
a bipartite graph is at most 1 and it cannot predict k-factors for any k≥3.There is also research on computational complexity of
toughness. In general, recognizing toughness of a graph is NP-hard [12]. Furthermore, 1-tough of
graphs is also NP-hard [13],
and even 1-tough of bipartite graphs is NP-hard [14] too. Toughness in claw-free
(K1,3-free) graphs [15], 1-tough in split graphs
[14], and toughness in
split graphs [16] have
been shown in P. In the future, it would be very interesting to determine the
complexity of bipartite toughness.



---

*Source: 597408-2009-01-06.xml*