Independent Set Neighborhood Union And Fractional Critical Deleted Graphs

Independent Set Neighborhood Union And Fractional Critical Deleted Graphs

Yun Gao

, Mohammad Reza Farahani

, Wei Gao

Received 28 June 2016

Abstract

A graph G is called a fractional (k; n⁰; m)-critical deleted graph if any n⁰ vertices are removed from G the resulting graph is a fractional (k; m)-deleted graph. In this paper, we determine that for integers k 1, i 2, n⁰; m 0, n >4ki+n⁰+ 4m 4, and (G) k(i 1) +n⁰+ 2m, if

jNG(x1)[NG(x2)[ [NG(xi)j n+n⁰ 2

for any independent subsetfx1; x2; : : : ; xigofV(G), thenGis a fractional(k; n⁰; m)- critical deleted graph. The bound for independent set neighborhood union con- dition is sharp.

1 Introduction

The fractional factor problem can be regarded as a relaxation problem of the cardinality matching. It has wide applications in …elds such as combinatorial polyhedron, network design and scheduling. For instance, in a communication network, several large data packets were to be sent to certain destinations via multiple channels. We can improve the e¢ ciency of this task by dividing the large data packets into small parcels. The available distribution of data packets can be considered as a fractional ‡ow problem.

Moreover, it can be looked upon as a fractional factor problem if the sources and destinations of a network are di¤erent.

In theoretical model, the whole network can be expressed as a graph in which each vertex represents a site and each edge denotes a channel between two sites. In this setting, the framework of data transmission problem is the existence of fractional factor in the graph corresponding to a network.

All graphs considered in this paper are …nite, loopless, and without multiple edges.

LetGbe a graph with vertex setV(G)and edge setE(G). For anyx2V(G), the degree and the neighborhood of xin G are denoted by d_G(x) and N_G(x), respectively. For

Mathematics Sub ject Classi…cations: 05C70.

yDepartment of Editorial, Yunnan Normal University, Kunming 650092, P. R. China

zDepartment of Applied Mathematics, Iran University of Science and Technology, Narmak, Tehran 16844, Iran

xSchool of Information Science and Technology, Yunnan Normal University, Kunming 650500, P.

R. China

268

S V(G), we denote byG[S]the subgraph ofGinduced byS, andG S =G[V(G)nS].

For two vertex-disjoint subsets S andT ofG, we use eG(S; T) to denote the number of edges with one end in S and the other end in T. We denote the minimum degree and the maximum degree ofGby (G)and (G), respectively. Thedistance dG(x; y) between two verticesxandyis de…ned to be the length of a shortest path connecting them. The notation and terminology used but unde…ned in this paper can be found in [1].

Let k 1 be an integer. A spanning subgraph F of G is called a k-factor if dF(x) = kfor each x2V(G). Leth:E(G)![0;1]be a function. If P

x2eh(e) =k for anyx2V(G), then we callG[F_h]afractionalk-factor ofGwith indicator function hwhereF_h=fe2E(G) :h(e)>0g. Zhou [10] introduced the concept of a fractional (k; m)-deleted graph, that is, a graph G is called a fractional (k; m)-deleted graph if removing anymedges fromG, the resulting graph has a fractionalk-factor. A fractional (k; m)-deleted graph is simply called a fractionalk-deleted graph ifm= 1. A graphG is called afractional (k; n⁰)-critical graph if after deleting anyn⁰ vertices fromG, the resulting graph still has a fractionalk-factor.

A graphGis called afractional(k; n⁰; m)-critical deleted graph if after deleting any n⁰ vertices fromG, the resulting graph is still a fractional(k; m)-deleted graph.

In what follows, we always assume that n = jV(G)j. Yu et al. [8] determined a degree condition for the existence of a fractionalk-factor as follows.

THEOREM 1 ([8]). Letk 1be an integer, and letGbe a connected graph with n 4k 3 and (G) k. If

maxfd_G(x); d_G(y)g n 2

for each pair of nonadjacent vertices x; yofG, thenGhas a fractionalk-factor.

Liu and Zhang [7] obtained the following toughness condition for a graph to have fractionalk-factors.

THEOREM 2 ([7]). Letk 2be an integer. A graphGof ordernwithn k+ 1 has a fractionalk-factor ift(G) k ¹_k.

For fractional(k; m)-deleted graphs, the following known results are stated by Zhou.

THEOREM 3 ([10]). Letk 2 andm 0be two integers. Let Gbe a connected graph with

n 9k 1 p

2(k 1)²+ 2 + 2(2k+ 1)m and (G) k+m+^(m+1)_4k^{2 1}. If

jNG(x)[NG(y)j 1

2(n+k 2)

for each pair of non-adjacent vertices x, y of G, thenG is a fractional(k; m)-deleted graph.

THEOREM 4 ([9]). Letk 1 andm 1be two integers. LetGbe a graph with n 4k 5 + 2(2k+ 1)m. If (G) ⁿ₂, thenGis a fractional(k; m)-deleted graph.

Recently, Gao et al. gave the following result on the neighborhood union condition for fractional(k; n⁰; m)-critical deleted graphs.

THEOREM 5. Let k 2 and n⁰; m 0 be three integers, and let G be a graph withn 8k+n⁰+ 4m 7and (G) k+n⁰+m. If

jNG(x)[NG(y)j n+n⁰ 2

for each pair of non-adjacent verticesx,y ofG, thenGis a fractional(k; n⁰; m)-critical deleted graph.

More su¢ cient conditions for graphs to have fractional factors can be found in Gao and Gao [3], Gao et al. [4], Gao and Wang [5], Zhou [10, 11, 12], and Zhou and Bian [13].

In this paper, we manifest the relationship between independent set neighborhood union condition and fractional (k; n⁰; m)-critical deleted graph. Furthermore, we will show that the bound for independent set neighborhood union is sharp in some sense.

Our main result is stated as follows.

THEOREM 6. Let Gbe a graph of ordern. Let k; i; n⁰; m be four integers with i 2,k 1 andm; n⁰ 0. If (G) k(i 1) + 2m+n⁰,n >4ki+n⁰+ 4m 4, and

jNG(x1)[NG(x2)[ [NG(xi)j n+n⁰ 2

for any independent subset fx₁; x₂; : : : ; x_ig ofV(G), thenGis a fractional (k; n⁰; m)- critical deleted graph.

Setn⁰ = 0in Theorem 6, then it becomes the following necessary independent set neighborhood union condition on fractional(k; m)-deleted graph.

COROLLARY 1. LetG be a graph of ordern. Let k; i; mbe three integers with i 2,k 1 andm 0. If (G) k(i 1) + 2m,n >4ki+ 4m 4, and

jN_G(x₁)[N_G(x₂)[ [N_G(x_i)j n 2

for any independent subset fx1; x2; : : : ; xig of V(G), then G is a fractional (k; m)- deleted graph.

Ifm= 0in Theorem 6, then we deduce the following corollary on the independent set neighborhood union condition of fractional (k; n⁰)-critical graph.

COROLLARY 2. LetG be a graph of ordern. Let k; i; n⁰ be three integers with i 2,k 1 andn⁰ 0. If (G) k(i 1) +n⁰,n >4ki+n⁰ 4, and

jNG(x1)[NG(x2)[ [NG(xi)j n+n⁰ 2

for any independent subset fx₁; x₂; : : : ; x_ig of V(G), then G is a fractional (k; n⁰)- critical graph.

In order to prove our main result, we need the following lemma which present the necessary and su¢ cient condition of fractional (k; n⁰; m)-critical deleted graph.

LEMMA 1 ([2]). Letk 1and n⁰; m 0 be three integers, and letGbe a graph andH a subgraph ofGwithmedges. ThenGis a fractional(k; n⁰; m)-critical deleted graph if and only if

G(S; T) =kjSj+X

x2T

dG S(x) kjTj kn⁰+X

x2T

dH(x) eH(S; T);

for all disjoint subsetsS andT ofV(G)withjSj n⁰.

Since our result refers to independent set neighborhood union condition, we need new tricks compare to Gao et al. [6].

2 Proof of Theorem 6

Assume to the contrary that Gsatis…es the conditions of the Theorem 6, but is not a fractional (k; n⁰; m)-critical deleted graph. By Lemma 1 and noting the fact that P

x2Td_H(x) e_G(T; S) 2m, there exist disjoint subsetsS andT ofV(G)such that

G(S; T) =kjSj+X

x2T

d_{G S}(x) kjTj kn⁰+ 2m 1: (1) We choose subsetsS andT such thatjTjis minimal. Obviously,T 6=;.

CLAIM 1. dG S(x) k 1 for anyx2T.

PROOF. Ifd_{G S}(x) k for some x2T, then the subsets S and T n fxg satisfy (1). This contradicts the choice ofS andT.

Let d1 = minfdG S(x)jx2 Tg and choose x1 2 T such that dG S(x1) =d1. If z 2andT n([^zj=1¹NT[xj])6=;, let

dz= minfdG S(x)jx2T n([^zj=1¹NT[xj])g

and choose x_z 2T n([^zj=1¹N_T[x_j]) such that d_{G S}(x_z) = d_z. So, we get a sequence such that0 d1 d2 d k 1and an independent setfx1; x2; : : : ; x g T.

CLAIM 2. jTj k(i 1) + 1.

PROOF. Assume thatjTj k(i 1). ThenjSj+d1 dG(x1) (G) k(i 1) + n⁰+ 2m. By (1) and 0 d1 k 1, we have

kn⁰+ 2m 1 kjSj+X

x2T

d_{G S}(x) kjTj kjSj+d1jTj kjTj

= kjSj+ (d1 k)jTj

k(k(i 1) d₁+n⁰+ 2m) + (d₁ k)(i 1)k

= k²(i 1) +d1(k(i 1) k) k²(i 1) +kn⁰+ 2km kn⁰+ 2m:

This produces a contradiction.

Sinced_{G S}(x) k 1 andjTj k(i 1) + 1, we get i. Thus, we can choose an independent setfx₁; x₂; : : : ; x_ig T.

In view of the condition of the theorem, we deduce n+n⁰

2 jN_G(x₁)[N_G(x₂)[ [N_G(x_i)j jSj+ Xi

j=1

d_j

and

jSj n+n⁰ 2

Xi

j=1

dj: (2)

Noting that

jNT[xj]j NT[xj]\([^jz=1¹NT[xz]) 1; j= 2;3; : : : ; i 1 and

j [^jz=1NT[xz]j Xj

z=1

jNT[xz]j Xj

z=1

(dG S(xz) + 1) = Xj

z=1

(dz+ 1); j= 1;2; : : : ; i:

Hence, we infer

kjSj+X

x2T

dG S(x) kjTj

kjSj kjTj+d₁jN_T[x₁]j+d₂(jN_T[x₂]j jN_T[x₂]\N_T[x₁]j) + +di 1(jNT[xi 1]j NT[xi 1]\([ⁱj=1²NT[xj]) ) +d_i(jTj j [ⁱj=1¹N_T[x_j])jj)

kjSj+ (d₁ d_i)jN_T[x₁]j+

i 1

X

j=2

d_j+ (d_i k)jTj d_i

i 1

X

j=2

jN_T[x_j]j

= kjSj+ (d₁ d_i)(d₁+ 1) +

i 1

X

j=2

d_j+ (d_i k)jTj d_i

i 1

X

j=2

(d_j+ 1)

= kjSj+d²₁+

i 1

X

j=1

d_j+ (d_i k)jTj d_i

i 1

X

j=1

(d_j+ 1);

which implies

(n jSj jTj)(k di) kjSj+X

x2T

d_{G S}(x) kjTj 2m kn⁰+ 1

kjSj+d²₁+

i 1

X

j=1

d_j+ (d_i k)jTj d_i

i 1

X

j=1

(d_j+ 1) 2m kn⁰+ 1:

Equivalently,

0 n(k d_i) (2k d_i)jSj+d_i

i 1

X

j=1

d_j

i 1

X

j=1

d_j+d_i(i 1) d²₁+ 2m kn⁰ 1: (3) By (2), (3),d₁ d₂ d_i k 1andn >4ki+n⁰+ 4m 4, we yield

0 n(k di) (2k di)(n+n⁰ 2

Xi

j=1

dj) +di i 1

X

j=1

dj i 1

X

j=1

dj

+di(i 1) d²₁+ 2m+kn⁰ 1

= n

2d_i+ 2k Xi

j=1

d_j d_i Xi

j=1

d_j+d_i

i 1

X

j=1

d_j

i 1

X

j=1

d_j

+di(i 1) d²₁+ 2m+n⁰di

2 1

= n

2d_i+ ((2k 1)d₁ d²₁) + (2k 1)

i 1

X

j=2

d_j

+di(2k+i 1) d²_i + 2m+n⁰di

2 1

n

2di+ (2k 1)di+ (2k 1)

i 1

X

j=2

di

+di(2k+i 1) d²_i + 2m+n⁰d_i

2 1

= n

2d_i+ 2kid_i d²_i + 2m+n⁰di

2 1:

Ifd_i>0, then0<2d_i d²_i 1 0sincen >4ki+n⁰+ 4m 4and2m(1 d_i) 0, a contradiction.

Ifd_i= 0, thend₁= =d_i= 0. By (2), we havejSj ⁿ⁺ⁿ2 ⁰ and jTj n jSj

n n⁰

2 . Sinced_{G S}(T) P

x2Td_H(x) e_G(T; S), we have kjSj+X

x2T

d_{G S}(x) kjTj (X

x2T

d_H(x) e_G(T; S)) kn⁰

k n+n⁰

2 k n n⁰

2 + (dG S(T) X

x2T

dH(x) +eG(T; S)) kn⁰ 0;

also a contradiction. This completes the proof of the theorem.

3 Sharpness

Theorem 6 is best possible, in some extent, on the conditions. Actually, we can con- struct some graphs such that the independent set neighborhood union condition in Theorem 6 can’t be replaced byjNG(x1)[NG(x2)[ [NG(xi)j ⁿ⁺ⁿ2 ⁰ 1.

LetG1=Kkt+n⁰be a complete graph,G2= (kt+1)K1be a graph consisting ofkt+1 isolated vertices, and G=G1_G2, wheret is su¢ ciently large (i.e.,t > ^2ki+2m_k ²+ n⁰ _2k¹ for somei. Thus, (G) k(i 1) +n⁰+ 2m, andn >4ki+n⁰+ 4m 4). Then n=jG1j+jG2j= 2kt+n⁰+ 1, and for any independent setfx1; x2; : : : ; xig V(G2), we have

n+n⁰

2 >jNG(x1)[NG(x2)[ [NG(xi)j=kt+n⁰> n+n⁰

2 1:

LetS=V(G₁), andT =V(G₂). Then

kjSj kjTj+d_{G S}(T) X

x2T

d_H(x) e_G(T; S)

! kn⁰

= kjSj kjTj kn⁰ =k(kt+n⁰) k(kt+ 1) kn⁰= k <0:

Hence,Gis not a fractional (k; n⁰; m)-critical deleted graph.

Acknowledgment. The research is partially supported by NSFC (no. 11401519).

The authors are grateful to the anonymous referee for a careful checking of the details and for helpful comments that improved this paper.

References

[1] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, Berlin, 2008.

[2] W. Gao, Some Results on Fractional Deleted Graphs, Doctoral Dissertation of Soochow University, 2012.

[3] W. Gao and Y. Gao, Toughness condition for a graph to be a fractional(g; f; n)- critical deleted graph, The Scienti…c World J. Vol. 2014, Article ID 369798, 7 pages, http://dx.doi.org/10.1155/2014/369798.

[4] W. Gao, L. Liang, T. W. Xu and J. X. Zhou, Tight toughness condition for fractional(g; f; n)-critical graphs, J. Korean Math. Soc., 51(2014), 55–65.

[5] W. Gao and W. F. Wang, Toughness and fractional critical deleted graph, Utilitas Math., 98(2015), 295–310.

[6] Y. Gao, M. R. Farahani and W. Gao, A neighborhood union condition for frac- tional (k; n⁰; m)-critical deleted graphs, Transactions on Combinatorics, 2016, In press.

[7] G. Liu and L. Zhang, Toughness and the existence of fractionalk-factors of graphs, Discrete Math., 308(2008), 1741–1748.

[8] J. Yu, G. Liu, M. Ma and B. Cao, A degree condition for graphs to have fractional factors, Adv. Math. (China), 35(2006), 621–628.

[9] S. Z. Zhou, A minimum degree condition of fractional (k; m)-deleted graphs, Comptes Rendus Math., 347(2009), 1223–1226.

[10] S. Z. Zhou, A neighborhood condition for graphs to be fractional (k; m)- deleted graphs, Glasgow Math. J., 52(2010), 33–40.

[11] S. Z. Zhou, A su¢ cient condition for a graph to be a fractional(f; n)-critical graph, Glasgow Math. J., 52(2010), 409–415.

[12] S. Z. Zhou, A su¢ cient condition for graphs to be fractional(k; m)-deleted graphs, Appl. Math. Lett., 24(2011), 1533–1538.

[13] S. Z. Zhou and Q. Bian, An existence theorem on fractional deleted graphs, Period.

Math. Hung., 71(2015), 125–133.