# Toughness Condition for a Graph to Be a Fractional(g

Authors: Wei Gao; Yun Gao
Journal: The Scientific World Journal
 (2014)

---

## Abstract

A graphG is called a fractional (
g
,
f
)-deleted graph if G
-
{
e
} admits a fractional (
g
,
f
)-factor for any e
∈
E
(
G
). A graph G is called a fractional (
g
,
f
,
n
)-critical deleted graph if, after deleting any n vertices from G, the resulting graph is still a fractional (
g
,
f
)-deleted graph. The toughness, as the parameter for measuring the vulnerability of communication networks, has received significant attention in computer science. In this paper, we present the relationship between toughness and fractional (
g
,
f
,
n
)-critical deleted graphs. It is determined that G is fractional (
g
,
f
,
n
)-critical deleted if t
(
G
)
≥
(
(b
2
-
1
+
b
n
)
/
a).


---

## Body

## 1. Introduction

All graphs considered in this paper are finite, are loopless, and are without multiple edges. The notation and terminology used but undefined in this paper can be found in [1]. Let G be a graph with the vertex set V
(
G
) and the edge set E
(
G
). For a vertex x
∈
V
(
G
), we use d
G
(
x
) and N
G
(
x
) to denote the degree and the neighborhood of x in G, respectively. Let δ
(
G
) denote the minimum degree of G. For any S
⊆
V
(
G
), the subgraph of G induced by S is denoted by G
[
S
].The problem of fractional factor can be considered as a relaxation of the well-known cardinality matching problem. It has wide-ranging applications in areas such as scheduling, network design, and the combinatorial polyhedron. For instance, several large data packets are to be sent to various destinations through several channels in a communication network. The efficiency of this work can be improved if large data packets are to be partitioned into small parcels. The feasible assignment of data packets can be seen as a fractional flow problem and it becomes a fractional factor problem when the destinations and sources of a network are disjoint.Suppose thatg and f are two integer-valued functions on V
(
G
) such that 0
≤
g
(
x
)
≤
f
(
x
) for all x
∈
V
(
G
). Afractional
(
g
,
f
)
-factor is a function h that assigns to each edge of a graph G a number in [0,1] so that for each vertex x we have g
(
x
)
≤
∑
e
∈
E
(
x
)
h
(
e
)
≤
f
(
x
). If g
(
x
)
=
a and f
(
x
)
=
b for all x
∈
V
(
G
), then a fractional (
g
,
f
)-factor is a fractional [
a
,
b
]-factor. Moreover, if g
(
x
)
=
f
(
x
)
=
k for all x
∈
V
(
G
), then a fractional (
g
,
f
)-factor is just a fractional k-factor. Throughout this paper, k
≥
1 is an integer, and we will not reiterate it again.A graphG is called afractional
(
g
,
f
,
n
)
-critical graph if, after deleting any n vertices from G, the resulting graph still has a fractional (
g
,
f
)-factor. A graph G is called afractional
(
g
,
f
,
m
)
-deleted graph if, after deleting any m edges, the resulting graph still has a (
g
,
f
)-factor. Fractional deleted graph and fractional critical graph, as extensions of the concept of fractional factor, describe the existence of fractional factor in communication networks when certain channels or certain sites are damaged.Gao [2] proposed a new concept to deal with the combination situation when some channels and some sites are unavailable in networks. A graph G is called afractional
(
g
,
f
,
n
,
m
)
-critical deleted graph if, after deleting any n vertices from G, the resulting graph is still a fractional (
g
,
f
,
m
)-deleted graph. In particular, the fractional (
g
,
f
,
n
,
m
)-critical deleted graph is just fractional (
g
,
f
,
n
)-critical deleted graph if m
=
1.Let(1)
ε
(
S
,
T
)
=
{
2
,
T
is
not
an
independent
set
1
,
T
is
an
independent
set
,
and
e
G
(
T
,
V
(
G
)
∖
(
S
∪
T
)
)
≥
1
0
,
otherwise
.
We heavily depend on the following lemma to prove our main result, which determined a necessary and sufficient condition for a graph to be a fractional (
g
,
f
,
n
)-critical deleted graph.Lemma 1 (Gao [2]).
LetG be a graph and let g
,
f be two nonnegative integer-valued functions defined on V
(
G
) satisfying g
(
x
)
≤
f
(
x
) for all x
∈
V
(
G
). Let n be a nonnegative integer. Then G is a fractional (
g
,
f
,
n
)-critical deleted graph if and only if
(2)
f
(
S
)
-
g
(
T
)
+
d
G
-
S
(
T
)
≥
max
⁡
{
f
(
U
)
:
U
⊆
S
,
|
U
|
=
n
}
+
ε
(
S
,
T
)
,
for any disjoint subsets S and T of V
(
G
) with |
S
|
≥
n.The notion oftoughness was first introduced by Chvátal in [3] to measure the vulnerable of networks: if G is complete graph, t
(
G
)
=
∞; if G is not complete,
(3)
t
(
G
)
=
min
⁡
{
|
S
|
ω
(
G
-
S
)
ω
(
G
-
S
)
≥
2
}
,
where ω
(
G
-
S
) is the number of connected components of G
-
S.Liu and Zhang [4] determined a necessary and sufficient condition for a graph to have a fractional (
g
,
f
)-factor. For several characters on fractional (
g
,
f
)-factor one can refer to Liu and Zhang [4, 5] for more details. Liu [6] investigated the necessary and sufficient condition for a graph G to be a fractional (
g
,
f
,
n
)-critical graph. For more recent results for fractional deleted graph and fractional critical graph one can refer to [7–12].Some toughness conditions for a graph to have a fraction factor were given in [13, 14]. Liu et al. [6] studied the relationship between toughness and fractional (
g
,
f
,
n
)-critical graphs and proved that G is a fractional (
g
,
f
,
n
)-critical graph if t
(
G
)
≥
(
(
b
2
-
1
)
(
n
+
1
)
/
a
) for a
≤
g
(
x
)
≤
f
(
x
)
≤
b with 1
≤
a
≤
b and b
≥
2. Zhou et al. [15] studied the toughness condition for fractional (k
,
m)-deleted graph. It is determined that G is a fractional (k
,
m)-deleted graph if t
(
G
)
≥
k
+
(
(
2
m
-
1
)
/
k
). Recently, in [16], Gao et al. derived a new bound for graphs to be fractional (
g
,
f
,
n
)-critical. It is verified that G is a fractional (
g
,
f
,
n
)-critical graph if t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
). This inspires us to think about the t
(
G
) for fractional (
g
,
f
,
n
)-critical deleted graphs. In this paper, we determine that such bound of toughness as above is sufficient for a graph G to be a fractional (
g
,
f
,
n
)-critical deleted graph. Our main result to be proved in next section can be stated as follows.Theorem 2.
LetG be a graph and let g
,
f be two integer-valued functions defined on V
(
G
) satisfying a
≤
g
(
x
)
≤
f
(
x
)
≤
b with 1
≤
a
≤
b and b
≥
2 for all x
∈
V
(
G
), where a, b are positive integers. Let n be a nonnegative integer. |
V
(
G
)
|
≥
n
+
b
+
2 if G is complete. If t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
), then G is a fractional (
g
,
f
,
n
)-critical deleted graph.Clearly, our result strengthened the previous conclusions, and it is sharp ifa
=
b and n
=
0 according to the sharpness example in Liu and Zhang [17]. The proof strategy is similar to the one in Liu and Zhang [17], but we need to cope with the more detailed case now and hence new methods are necessary. Before proving Theorem 2, we would like to show some useful lemmas.Lemma 3 (Chvátal [3]).
If a graphG is not complete, then t
(
G
)
≤
(
1
/
2
)
δ
(
G
).Lemma 4 (Liu and Zhang [17]).
LetG be a graph and let H
=
G
[
T
] such that δ
(
H
)
≥
1 and 1
≤
d
G
(
x
)
≤
k
-
1 for every x
∈
V
(
H
), where T
⊆
V
(
G
) and k
≥
2. Let T
1
,
…
,
T
k
-
1 be a partition of the vertices of H satisfying d
G
(
x
)
=
j for each x
∈
T
j, where one allows some T
j to be empty. If each component of H has a vertex of degree at most k
-
2 in G, then H has a maximal independent set I and a covering set C
=
V
(
H
)
-
I such that
(4)
∑
j
=
1
k
-
1
‍
(
k
-
j
)
c
j
≤
∑
j
=
1
k
-
1
‍
(
k
-
2
)
(
k
-
j
)
i
j
,
where c
j
=
|
C
∩
T
j
| and i
j
=
|
I
∩
T
j
| for every j
=
1
,
…
,
k
-
1.The lemma below can be deduced from Lemma 2.2 in [17].Lemma 5 (Liu and Zhang [17]).
LetG be a graph and let H
=
G
[
T
] such that d
G
(
x
)
=
k
-
1 for every x
∈
V
(
H
) and no component of H is isomorphic to K
k, where T
⊆
V
(
G
) and k
≥
2. Then there exist an independent set I and the covering set C
=
V
(
H
)
-
I of H satisfying
(5)
|
V
(
H
)
|
≤
∑
i
=
1
k
‍
(
k
-
i
+
1
)
|
I
(
i
)
|
-
|
I
(
1
)
|
2
,
|
C
|
≤
∑
i
=
1
k
‍
(
k
-
i
)
|
I
(
i
)
|
-
|
I
(
1
)
|
2
,
where I
(
i
)
=
{
x
∈
I
,
d
H
(
x
)
=
k
-
i
}, 1
≤
i
≤
k, and ∑
i
=
1
k
|
I
(
i
)
|
=
|
I
|.


## 2. Proof of Theorem2

IfG is complete, then G is a fractional (
g
,
f
,
n
)-critical deleted graph due to |
V
(
G
)
|
≥
n
+
b
+
2. In what follows, we assume that G is not complete.Suppose thatG satisfies the conditions of Theorem 2 but is not a fractional (
g
,
f
,
n
)-critical graph. By Lemma 1 and ε
(
S
,
T
)
≤
2, there exist subsets S and T of V
(
G
) such that
(6)
a
|
S
|
+
∑
x
∈
T
‍
d
G
-
S
(
x
)
-
b
|
T
|
≤
f
(
S
)
-
g
(
T
)
+
d
G
-
S
(
T
)
≤
b
n
+
1
.
We choose subsets S and T such that |
T
| is minimum. Obviously, we deduce T
≠
∅ and d
G
-
S
(
x
)
≤
g
(
x
)
-
1
≤
b
-
1 for any x
∈
T.Letl be the number of the components of H
′
=
G
[
T
] which are isomorphic to K
b and let T
0
=
{
x
∈
V
(
H
′
)
∣
d
G
-
S
(
x
)
=
0
}. Let H be the subgraph obtained from H
′
-
T
0 by deleting those l components isomorphic to K
b.If|
V
(
H
)
|
=
0, then by virtue of (6) we infer
(7)
a
|
S
|
≤
b
|
T
0
|
+
b
l
+
b
n
+
1
,
or
(8)
|
S
|
≤
b
(
|
T
0
|
+
l
)
+
b
n
+
1
a
.
If ω
(
G
-
S
)
=
|
T
0
|
+
l
>
1, then t
(
G
)
≤
(
|
S
|
/
ω
(
G
-
S
)
)
≤
(
(
b
(
|
T
0
|
+
l
)
+
b
n
+
1
)
/
a
(
|
T
0
|
+
l
)
)
<
(
(
b
+
b
n
+
1
)
/
a
), which contradicts t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
) and b
≥
2. If ω
(
G
-
S
)
=
|
T
0
|
+
l
=
1, then |
T
0
|
+
l
=
1. Since d
G
-
S
(
x
)
+
|
S
|
≥
d
G
(
x
)
≥
δ
(
G
)
≥
2
t
(
G
), we have 2
t
(
G
)
≤
b
-
1
+
|
S
|
≤
b
-
1
+
(
(
b
(
n
+
1
)
+
1
)
/
a
), which contradicts t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
).Now we consider that|
V
(
H
)
|
>
0. Let H
=
H
1
∪
H
2, where H
1 is the union of components of H which satisfies that d
G
-
S
(
x
)
=
b
-
1 for every vertex x
∈
V
(
H
1
) and H
2
=
H
-
H
1. In terms of Lemma 5, H
1 has a maximum independent set I
1 and the covering set C
1
=
V
(
H
1
)
-
I
1 such that
(9)
|
V
(
H
1
)
|
≤
∑
i
=
1
b
‍
(
b
-
i
+
1
)
|
I
(
i
)
|
-
|
I
(
1
)
|
2
,
|
C
1
|
≤
∑
i
=
1
b
‍
(
b
-
i
)
|
I
(
i
)
|
-
|
I
(
1
)
|
2
,
where I
(
i
)
=
{
x
∈
I
1
,
d
H
1
(
x
)
=
b
-
i
}, 1
≤
i
≤
b, and ∑
i
=
1
b
|
I
(
i
)
|
=
|
I
1
|. Let T
j
=
{
x
∈
V
(
H
2
)
∣
d
G
-
S
(
x
)
=
j
} for 1
≤
j
≤
b
-
1. Each component of H
2 has a vertex of degree at most b
-
2 in G
-
S by the definitions of H and H
2. According to Lemma 4, H
2 has a maximal independent set I
2 and the covering set C
2
=
V
(
H
2
)
-
I
2 such that
(10)
∑
j
=
1
b
-
1
‍
(
b
-
j
)
c
j
≤
∑
j
=
1
b
-
1
‍
(
b
-
2
)
(
b
-
j
)
i
j
,
where c
j
=
|
C
2
∩
T
j
| and i
j
=
|
I
2
∩
T
j
| for every j
=
1
,
…
,
b
-
1. Set W
=
V
(
G
)
-
S
-
T and U
=
S
∪
C
1
∪
(
N
G
(
I
1
)
∩
W
)
∪
C
2
∪
(
N
G
(
I
2
)
∩
W
). We infer
(11)
|
U
|
≤
|
S
|
+
|
C
1
|
+
∑
j
=
1
b
-
1
‍
j
i
j
+
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
,
ω
(
G
-
U
)
≥
t
0
+
l
+
|
I
1
|
+
∑
j
=
1
b
-
1
‍
i
j
,
where t
0
=
|
T
0
|. Let t
(
G
)
=
t. Then when ω
(
G
-
U
)
>
1, we have
(12)
|
U
|
≥
t
ω
(
G
-
U
)
,
and it also holds when ω
(
G
-
U
)
=
1. In terms of (11) and (12), we get
(13)
|
S
|
+
|
C
1
|
≥
∑
j
=
1
b
-
1
‍
(
t
-
j
)
i
j
+
t
(
t
0
+
l
)
+
t
|
I
1
|
-
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
.
In view of b
|
T
|
-
d
G
-
S
(
T
)
≥
a
|
S
|
-
b
n
-
1, we obtain
(14)
b
t
0
+
b
l
+
|
V
(
H
1
)
|
+
∑
j
=
1
b
-
1
‍
(
b
-
j
)
i
j
+
∑
j
=
1
b
-
1
‍
(
b
-
j
)
c
j
≥
a
|
S
|
-
b
n
-
1
.
Combining with (13), we deduce
(15)
b
t
0
+
b
l
+
|
V
(
H
1
)
|
+
∑
j
=
1
b
-
1
‍
(
b
-
j
)
i
j
+
∑
j
=
1
b
-
1
‍
(
b
-
j
)
c
j
+
a
|
C
1
|
+
b
n
+
1
≥
∑
j
=
1
b
-
1
‍
(
a
t
-
a
j
)
i
j
+
a
t
(
t
0
+
l
)
+
a
t
|
I
1
|
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
.
Therefore,
(16)
|
V
(
H
1
)
|
+
∑
j
=
1
b
-
1
‍
(
b
-
j
)
c
j
+
a
|
C
1
|
≥
∑
j
=
1
b
-
1
‍
(
a
t
-
a
j
-
b
+
j
)
i
j
+
(
a
t
-
b
)
(
t
0
+
l
)
+
a
t
|
I
1
|
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
-
b
n
-
1
.
By virtue of (9), we have
(17)
|
V
(
H
1
)
|
+
a
|
C
1
|
≤
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
-
(
a
+
1
)
|
I
(
1
)
|
2
.
Using (10), (16), and (17), we get
(18)
∑
j
=
1
b
-
1
‍
(
b
-
2
)
(
b
-
j
)
i
j
+
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
∑
j
=
1
b
-
1
‍
(
a
t
-
a
j
-
b
+
j
)
i
j
+
a
t
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
(
a
t
-
b
)
(
t
0
+
l
)
-
b
n
-
1
.The following proof splits into two cases by the value oft
0
+
l.Case 1 (t
0
+
l
≥
1).
Bya
t
≥
b
2
-
1
+
b
n, we have (
a
t
-
b
)
(
t
0
+
l
)
-
b
n
-
1
≥
b
2
-
b
-
2
≥
0. Hence, (18) becomes
(19)
∑
j
=
1
b
-
1
(
b
-
2
)
(
b
-
j
)
i
j
+
∑
i
=
1
b
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
∑
j
=
1
b
-
1
(
a
t
-
a
j
-
b
+
j
)
i
j
+
a
t
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
(
i
-
1
)
|
I
(
i
)
|
.
And then, at least one of the following two cases must hold.Subcase 1 (∑
j
=
1
b
-
1
(
b
-
2
)
(
b
-
j
)
i
j
≥
∑
j
=
1
b
-
1
(
a
t
-
a
j
-
b
+
j
)
i
j).
There is at least onej such that
(20)
(
b
-
2
)
(
b
-
j
)
≥
a
t
-
a
j
-
b
+
j
,
which implies
(21)
a
t
≤
(
b
-
2
)
(
b
-
j
)
+
a
j
+
b
-
j
=
b
(
b
-
2
)
+
(
a
-
b
+
1
)
j
+
b
.
If a
=
b, then a
t
≤
a
(
a
-
2
)
+
j
+
a
≤
a
2
-
1. By t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
), we get n
=
0 and ∑
j
=
1
b
-
2
‍
i
j
=
0, which contradicts the definition of H
2 and the choice of I
2 (see Lemma 4 proof in [17] such that ∑
j
=
1
b
-
2
‍
i
j
≠
0).
Ifa
<
b, then a
t
≤
b
(
b
-
2
)
+
(
a
-
b
+
1
)
+
b
=
(
b
2
-
1
)
+
(
a
-
b
)
+
(
2
-
b
)
<
b
2
-
1, which contradicts t
(
G
)
≥
(
(
b
2
-
1
+
b
n
)
/
a
).Subcase 2 (∑
i
=
1
b
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
a
t
|
I
1
|
+
(
(
a
+
1
)
|
I
(
1
)
|
/
2
)
-
a
∑
i
=
1
b
(
i
-
1
)
|
I
(
i
)
|).
Ift
0
+
l
≥
2 or b
≥
3, then by (
b
t
-
a
)
(
t
0
+
l
)
-
b
n
-
1
≥
1 we have
(22)
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
a
t
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
1
≥
(
b
2
-
1
+
b
n
)
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
1
≥
(
b
2
-
1
)
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
1
,
∑
i
=
2
b
‍
(
a
b
+
b
-
a
-
i
+
2
-
b
2
)
|
I
(
i
)
|
+
(
a
b
+
b
-
3
2
a
-
b
2
+
1
2
)
|
I
(
1
)
|
≥
1
.
Let
(23)
h
1
(
b
)
=
-
b
2
+
(
a
+
1
)
b
-
3
2
a
+
1
2
.
From b
≥
a and h
1
(
2
)
<
0, if a
=
1, we deduce
(24)
max
⁡
{
h
1
(
b
)
}
=
h
1
(
a
)
=
-
a
2
+
1
2
<
0
.
Furthermore, a
b
+
b
-
a
-
i
+
2
-
b
2
≤
-
b
2
+
(
a
+
1
)
b
-
a due to i
≥
2. Let
(25)
h
2
(
b
)
=
-
b
2
+
(
a
+
1
)
b
-
a
.
From b
≥
a, we infer
(26)
max
⁡
{
h
2
(
b
)
}
=
h
2
(
a
)
=
0
.
This is a contradiction.
Ifn
≥
1, we obtain
(27)
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
(
b
2
-
1
+
b
n
)
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
≥
(
b
2
-
1
)
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
2
.
Hence,
(28)
∑
i
=
2
b
‍
(
a
b
+
b
-
a
-
i
+
2
-
b
2
)
|
I
(
i
)
|
+
(
a
b
+
b
-
3
2
a
-
b
2
+
1
2
)
|
I
(
1
)
|
≥
2
,
a contradiction.
In conclusion, we haven
=
0, t
0
+
l
=
1, and (
a
,
b
)
=
(
2,2
) (if (
a
,
b
)
=
(
1,2
), then h
1
<
0 and h
2
<
0, a contradiction). Then the result follows from the main result in [18] which determined that G is fractional 2-deleted graph if t
(
G
)
≥
(
3
/
2
).Case 2 (t
0
+
l
=
0).
In this case, (18) becomes
(29)
∑
j
=
1
b
-
1
‍
(
b
-
2
)
(
b
-
j
)
i
j
+
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
∑
j
=
1
b
-
1
‍
(
a
t
-
a
j
-
b
+
j
)
i
j
+
a
t
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
-
b
n
-
1
.Subcase 1 (|
I
1
|
=
0). In this subcase, (29) becomes
(30)
∑
j
=
1
b
-
1
‍
(
(
b
-
2
)
(
b
-
j
)
-
(
a
t
-
a
j
-
b
+
j
)
)
i
j
+
b
n
+
1
≥
0
.
Let
(31)
h
j
=
(
b
-
2
)
(
b
-
j
)
-
(
a
t
-
a
j
-
b
+
j
)
=
b
2
+
(
a
-
b
+
1
)
j
-
b
-
a
t
≤
b
2
+
(
a
-
b
+
1
)
j
-
b
-
a
·
b
2
-
1
+
b
n
a
=
(
a
-
b
+
1
)
j
-
b
+
1
-
b
n
.(i) Ifb
≥
a
+
1, then
(32)
(
a
-
b
+
1
)
j
-
b
+
1
-
b
n
≤
a
-
2
b
+
2
-
b
n
≤
-
b
+
1
-
b
n
=
-
b
n
-
1
.
This implies (
a
,
b
)
=
(
1,2
), ∑
j
=
2
b
-
1
‍
i
j
=
0, |
C
2
|
≤
|
I
2
|, and |
T
|
≤
2
|
I
2
|. Thus,
(33)
|
S
|
≤
2
|
I
2
|
(
b
-
1
)
+
b
n
+
1
a
.
If |
I
2
|
=
1, then |
S
|
≤
(
(
2
(
b
-
1
)
+
b
n
+
1
)
/
a
)
=
3
+
2
n and δ
(
G
)
≤
|
S
|
+
1
≤
4
+
2
n. This contradicts δ
(
G
)
≥
2
t
(
G
)
≥
6
+
4
n. Hence, |
I
2
|
≥
2.LetZ
=
{
x
∣
x
∈
C
2
,
d
G
-
S
(
x
)
=
1
} and z
=
|
Z
|. Thus, 0
≤
z
≤
|
I
2
| and N
G
-
S
(
v
)
∈
I
2 if v
∈
Z. We obtain
(34)
|
S
|
≤
(
|
I
2
|
+
z
)
(
b
-
1
)
+
(
|
C
2
|
-
z
)
(
b
-
2
)
+
b
n
+
1
a
.
Letting Z
′
=
{
x
∣
x
∈
N
G
(
I
2
)
∩
W
,
d
G
-
S
(
x
)
=
1
}, we infer
(35)
b
2
-
1
+
b
n
a
≤
t
(
G
)
≤
|
U
-
Z
∪
Z
′
|
ω
(
G
-
(
U
-
Z
∪
Z
′
)
)
≤
(
(
|
I
2
|
+
z
)
(
b
-
1
)
+
(
|
C
2
|
-
z
)
(
b
-
2
)
+
b
n
+
1
a
+
(
|
C
2
|
-
z
)
+
(
|
I
2
|
-
|
C
2
|
)
(
|
C
2
|
-
z
)
a

)
×
|
I
2
|
-
1
.
By (
a
,
b
)
=
(
1,2
) and |
C
2
|
≤
|
I
2
|, we get 2
n
(
1
-
(
1
/
|
I
2
|
)
)
≤
(
1
/
|
I
2
|
)
-
1. By |
I
2
|
≥
2, we derive the contradiction.(ii) Ifa
=
b, then max
⁡
{
h
j
}
=
h
b
-
1
=
-
b
n and the second largest value of h
j is h
b
-
2
=
-
b
n
-
1. In terms of the analysis of Lemma 4 in [17]: for each connected component of H
2, choose a vertex with the smallest degree and add it to I
2. Hence, by the definition of H
2, we confirm that H
2 is connected; each vertex in I
2 has degree b
-
1 in G
-
S except that one vertex has degree b
-
2 in G
-
S. This fact implies
(36)
|
C
2
|
≤
(
b
-
2
)
+
(
|
I
2
|
-
1
)
(
b
-
1
-
1
)
=
|
I
2
|
(
b
-
2
)
,
|
T
|
≤
|
I
2
|
(
b
-
1
)
,
|
S
|
≤
|
T
|
+
1
+
b
n
a
≤
|
I
2
|
+
1
-
|
I
2
|
b
+
n
.
If |
I
2
|
=
1, then |
S
|
≤
1
+
n and δ
(
G
)
≤
|
S
|
+
(
b
-
1
)
≤
b
+
n, which contradicts δ
(
G
)
≥
2
t
(
G
)
>
b
+
n. Hence, |
I
2
|
≥
2 and
(37)
b
-
1
b
+
n
≤
t
(
G
)
≤
|
U
|
ω
(
G
-
U
)
≤
(
(
1
-
|
I
2
|
)
/
b
)
+
|
I
2
|
+
|
I
2
|
(
b
-
2
)
+
n
|
I
2
|
=
(
b
-
1
-
1
b
)
+
1
b
|
I
2
|
+
n
|
I
2
|
.
This reveals n
(
1
-
(
1
/
|
I
2
|
)
)
≤
(
(
1
/
b
|
I
2
|
)
-
1
), which contradicts b
≥
2 and |
I
2
|
≥
2.Subcase 2 (|
I
2
|
=
0). In this subcase, (29) becomes
(38)
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
-
a
t
|
I
1
|
-
(
a
+
1
)
|
I
(
1
)
|
2
+
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
+
b
n
+
1
≥
0
.
This implies
(39)
∑
i
=
2
b
‍
(
a
b
+
b
-
a
-
i
+
2
-
b
2
)
|
I
(
i
)
|
+
(
a
b
+
b
-
3
2
a
-
b
2
+
1
2
)
|
I
(
1
)
|
+
1
≥
0
.
Then, by h
1
≤
-
1
/
2, we get ∑
i
=
4
b
|
I
(
i
)
|
=
0, |
I
(
3
)
|
≤
1, and |
I
(
1
)
|
≤
2. Now, we consider the following three subcases.Subcase
2
.1 (|
I
(
1
)
|
=
1). In this subcase, we have ∑
i
=
3
b
|
I
(
i
)
|
=
0. By analyzing the proof of Lemma 2.2 in [17]: “for each vertex x
∈
I
n and d
H
n
(
x
)
=
k
-
1, there exists a vertex y
∈
I
n such that N
H
n
(
x
)
∩
N
H
n
(
y
)
≠
∅,” we obtain |
I
1
|
≥
2,
(40)
|
T
|
≤
(
b
-
1
)
+
(
|
I
1
|
-
1
)
(
b
-
1
)
=
|
I
1
|
(
b
-
1
)
,
|
S
|
≤
|
T
|
+
1
+
b
n
a
≤
|
I
1
|
(
b
-
1
)
+
1
+
b
n
a
,
|
U
|
≤
|
S
|
+
|
C
1
|
+
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
≤
|
I
1
|
(
b
-
1
)
+
1
+
b
n
a
+
|
I
1
|
(
b
-
1
)
-
|
I
1
|
+
(
|
I
1
|
-
1
)
=
|
I
1
|
(
b
-
1
)
+
1
+
b
n
a
+
|
I
1
|
(
b
-
1
)
-
1
.
Thus,
(41)
b
2
-
1
+
b
n
a
≤
t
(
G
)
≤
|
U
|
ω
(
G
-
U
)
≤
(
(
|
I
1
|
(
b
-
1
)
+
1
+
b
n
)
/
a
)
+
|
I
1
|
(
b
-
1
)
-
1
|
I
1
|
.
This implies b
n
(
1
-
(
1
/
|
I
1
|
)
)
≤
(
b
-
a
)
(
1
-
b
)
+
(
(
1
-
a
)
/
|
I
1
|
), a contradiction.Subcase
2.2 (|
I
(
1
)
|
=
2). In this subcase, ∑
i
=
3
b
|
I
(
i
)
|
=
0. We can get a contradiction via a similar discussion as in Subcase 2.1.Subcase
2.3
(
|
I
(
1
)
|
=
0). In this subcase, we have ∑
i
=
4
b
|
I
(
i
)
|
=
0 and |
I
(
3
)
|
≤
1. If |
I
1
|
=
1, then |
S
|
≤
(
(
(
b
-
1
)
+
b
n
+
1
)
/
a
). Thus, we infer
(42)
(
b
-
1
)
+
b
n
+
1
a
+
b
-
1
≥
b
-
1
+
|
S
|
≥
δ
(
G
)
≥
2
t
(
G
)
≥
2
(
b
2
-
1
+
b
n
)
a
,
a contradiction. Hence, |
I
1
|
≥
2. Let Y
=
N
G
(
I
1
)
∩
W.If there is a vertexy
∈
Y such that y only adjacent to one vertex in I
1. Reset(43)
U
=
S
∪
C
1
∪
(
N
G
(
I
1
)
∩
(
W
-
{
y
}
)
)
.
Then, we have
(44)
|
U
|
≤
|
S
|
+
|
I
1
|
(
b
-
1
)
-
1
≤
|
I
1
|
(
b
-
1
)
+
1
+
b
n
a
+
|
I
1
|
(
b
-
1
)
-
1
.
By |
I
1
|
≥
2, we obtain
(45)
b
2
-
1
+
b
n
a
≤
t
(
G
)
≤
|
U
|
ω
(
G
-
U
)
≤
(
(
|
I
1
|
(
b
-
1
)
+
1
+
b
n
)
/
a
)
+
|
I
1
|
(
b
-
1
)
-
1
|
I
1
|
.
This implies b
n
(
1
-
(
1
/
|
I
1
|
)
)
≤
(
b
-
a
)
(
1
-
b
)
+
(
(
1
-
a
)
/
|
I
1
|
), a contradiction.If each vertex inY is adjacent to at least two vertices in I
1, we get(46)
|
U
|
≤
|
S
|
+
|
I
1
|
(
b
-
2
)
+
|
I
1
|
2
≤
|
I
1
|
(
b
-
1
)
+
1
+
b
n
a
+
|
I
1
|
(
b
-
2
)
+
|
I
1
|
2
,
where U
=
S
∪
C
1
∪
(
N
G
(
I
1
)
∩
W
). Due to |
I
1
|
≥
2, we deduce
(47)
b
2
-
1
+
b
n
a
≤
t
(
G
)
≤
|
U
|
ω
(
G
-
U
)
≤
(
(
|
I
1
|
(
b
-
1
)
+
1
+
b
n
)
/
a
)
+
|
I
1
|
(
b
-
2
)
+
(
|
I
1
|
/
2
)
|
I
1
|
.
That is to say, b
n
(
1
-
(
1
/
|
I
1
|
)
)
≤
(
b
-
a
)
(
1
-
b
)
+
(
(
1
/
|
I
1
|
)
-
(
a
/
2
)
), which contradicts a
≥
1 and |
I
1
|
≥
2.Subcase 3 (|
I
1
|
≠
0 and |
I
2
|
≠
0). From what we have discussed in Subcase 1, we get ∑
j
=
1
b
-
1
(
b
-
2
)
(
b
-
j
)
i
j
≤
∑
j
=
1
b
-
1
(
a
t
-
a
j
-
b
+
j
)
i
j
+
b
n
+
1. Then, we deduce
(48)
∑
i
=
1
b
‍
(
a
b
-
a
i
+
b
-
i
+
1
)
|
I
(
i
)
|
≥
a
t
|
I
1
|
+
(
a
+
1
)
|
I
(
1
)
|
2
-
a
∑
i
=
1
b
‍
(
i
-
1
)
|
I
(
i
)
|
.
This implies
(49)
∑
i
=
2
b
‍
(
a
b
+
b
-
a
-
i
+
2
-
b
2
)
|
I
(
i
)
|
+
(
a
b
+
b
-
3
2
a
-
b
2
+
1
2
)
|
I
(
1
)
|
≥
0
.
Thus, we have ∑
i
=
4
b
|
I
(
i
)
|
=
0, |
I
(
3
)
|
≤
1, |
I
(
1
)
|
≤
2, and n
=
0, by what we have discussed in Subcase 2. It is enough to discuss the situation of |
I
(
1
)
|
=
0; other two cases for |
I
(
1
)
|
=
1 and |
I
(
1
)
|
=
2 can be considered in a similar way.Under the condition of|
I
(
1
)
|
=
0, we get ∑
i
=
4
b
|
I
(
i
)
|
=
0, |
I
(
3
)
|
≤
1,
(50)
|
T
|
≤
|
I
1
|
(
b
-
1
)
+
|
I
2
|
(
b
-
1
)
=
(
b
-
1
)
(
|
I
1
|
+
|
I
2
|
)
,
|
S
|
≤
|
T
|
+
1
a
≤
(
|
I
1
|
+
|
I
2
|
)
(
b
-
1
)
+
1
a
.
Since |
I
1
|
+
|
I
2
|
≥
2, we get
(51)
b
2
-
1
a
≤
t
(
G
)
≤
|
U
|
ω
(
G
-
U
)
≤
|
S
|
+
|
I
2
|
(
b
-
2
)
+
|
I
1
|
(
b
-
1
)
|
I
1
|
+
|
I
2
|
.
Hence,
(52)
(
b
2
-
1
)
(
|
I
1
|
+
|
I
2
|
)
≤
(
|
I
1
|
+
|
I
2
|
)
(
b
-
1
)
+
1
+
(
a
b
-
2
a
)
(
|
I
1
|
+
|
I
2
|
)
+
|
I
1
|
a
.
This implies (
b
-
a
)
(
b
-
1
)
(
|
I
1
|
+
|
I
2
|
)
≤
1
-
a
|
I
2
|, a contradiction.We complete the proof of the theorem.



---

*Source: 369798-2014-07-09.xml*