PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 205–212 https://doi.org/10.2298/PIM1715205Y

NEIGHBOURHOOD CONDITIONS FOR FRACTIONAL ID-[A, B]-FACTOR-CRITICAL GRAPHS

Yuan Yuan and Zhiren Sun

Abstract. A graph G is fractional ID-[a, b]-factor-critical if G − I has a fractional [a, b]-factor for every independent set I of G. We extend a result of Zhou and Sun concerning fractional ID-k-factor-critical graphs.

1. Introduction

The graphs considered in this paper will be finite and undirected simple graphs. Let G be a graph with vertex set V (G) and edge set E(G). For any vertex x of G, we use d_{G}(x) and N_{G}(x) to denote the degree of x in G and the neighbourhood of x in G, respectively.

Let a and b be two integers with 2 ⩽ a ⩽ b. A spanning subgraph F of G is called an [a, b]-factor if a ⩽ d_{F} (x) ⩽ b for each x ∈ V (G). If a = b = k, then an [a, b]-factor is called a k-factor.

Let h: E(G) → [0, 1] be a function. If a ⩽ ∑ _{x∈e} h(e) ⩽ b holds for any x ∈ V (G), then we call G[F_{h}] a fractional [a, b]-factor of G with indicator function h where F_{h} = {e ∈ E(G) : h(e) > 0}. If a = b = k, then a fractional [a, b]-factor is called a fractional k-factor. A graph G is fractional ID-[a, b]-factor-critical if G − I has a fractional [a, b]-factor for every independent set I of G.

Many authors have investigated [a, b]-factors [3, 4, 6–8] and fractional factors [9, 11]. The following results on fractional ID-k-factor-critical and fractional ID- [a, b]-factor-critical graphs are known.

Theorem 1.1. Let G be a graph, and let k be an integer with k ⩾ 1. If

α(G) ⩽ \frac{4k(δ(G) − k + 1)}{k^{2} + 6k + 1} ,

then G is fractional ID-k-factor-critical.

ID-[a, b]-factor-critical graph.

Communicated by Slobodan Simić.

2010 Mathematics Subject Classification: Primary 05C70.

Key words and phrases: graph, neighbourhood condition, fractional [a, b]-factor, fractional

Theorem 1.2. Let k be an integer with k ⩾ 2, and let G be a graph of order n with n ⩾ 9k − 14. Suppose for any subset X ⊂ V (G), we have

N_{G}(X) = V (G) if |X| ⩾ ⌊ \frac{kn}{3k − 1} ⌋; or
|N_{G}(X)| ⩾ \frac{3k − 1}{k} |X| if |X| < ⌊ \frac{kn}{3k − 1} ⌋.

Then G is fractional ID-k-factor-critical.

Theorem 1.3. Let G be a graph of order n, and let a and b be two integers with 1 ⩽ a ⩽ b. If n ⩾ \frac{(a+2b)(a+b−2)+1}{b} and δ(G) ⩾ \frac{(a+b)n}{a+2b} , then G is fractional ID-[a, b]-factor-critical.

In this paper, we study fractional ID-[a, b]-factor-critical graph, and then get a neighbourhood condition for a graph to be fractional ID-[a, b]-factor-critical, which is an extension of Theorem 1.2.

2. Main result

We first show the main result in this paper.

Theorem 2.1. Let a and b be two integers with 2 ⩽ a ⩽ b, and let G be a graph of order n with n > 1 + \frac{(a+2b−1)(2a+b−4)}{b} . Suppose that for any subset X ⊂ V (G), we have

N_{G}(X) = V (G) if |X| ⩾ ⌊ \frac{bn}{a + 2b − 1} ⌋; or
|N_{G}(X)| ⩾ \frac{a + 2b − 1}{b} |X| if |X| < ⌊ \frac{bn}{a + 2b − 1} ⌋.

Then G is fractional ID-[a, b]-factor-critical.

We give two lemmas which play an important role in the proof of Theorem 2.1.

Lemma 2.1. Let G be a graph. Then G has a fractional [a, b]-factor if and only if for every subset S of V (G), we have δ_{G}(S, T) = b|S|+d_{G−S} (T)−a|T | ⩾ 0, where T = {x : x ∈ V (G) ∖ S, d_{G−S} (x) ⩽ a − 1} and d_{G−S} (T) = ∑ _{x∈T} d_{G−S} (x).

Lemma 2.2. Let G be a graph which satisfies the assumption of Theorem 2.1. Then δ(G) ⩾ \frac{(a+b−1)n+b}{a+2b−1} .

Proof. Suppose that x is a vertex of G with degree δ(G). Set X = V (G) ∖ N_{G}(x). Notice that x ∉ N_{G}(X) and N_{G}(X) ≠ V (G). Hence, we obtain

n − 1 ⩾ |N_{G}(X)| ⩾ \frac{a + 2b − 1}{b} |X|,

which implies

(2.1)  |X| ⩽ \frac{b(n − 1)}{a + 2b − 1} .

Using (2.1) and |X| = n − δ(G), we have n − δ(G) ⩽ \frac{b(n−1)}{a+2b−1} , wherefrom

δ(G) ⩾ n − \frac{b(n − 1)}{a + 2b − 1} = \frac{n(a + b − 1) + b}{a + 2b − 1} .

Thus, Lemma 2.2 holds. □

Proof of Theorem 2.1. Let I be an independent set of G and H = G − I. We prove the theorem by contradiction. Suppose that H has no fractional [a, b]- factor. By Lemma 2.1, there exists some subset S ⊂ V (H) such that

(2.2)  δ_{H} (S, T) = b|S| + d_{H−S} (T) − a|T | ⩽ −1.

We choose S and T such that |T | is as small as possible. According to (2.2) and H = G − I, we obtain

(2.3)  δ_{H} (S, T) = b|S| + d_{G−I−S} (T) − a|T | ⩽ −1,

where T = {x : x ∈ V (G) ∖ (I ∪ S), d_{G−I−S} (x) ⩽ a − 1}.

If T = ϕ, then from (2.3), we have −1 ⩾ δ_{H} (S, T) = b|S| ⩾ 0, a contradiction. Hence, T ≠ ϕ. Define h = min{d_{G−I−S} (x) : x ∈ T } and choose x_{1} ∈ T subject to d_{G−I−S} (x_{1}) = h. According to the definition of T, we have 0 ⩽ h ⩽ a − 1. Obviously, it holds that

δ(G) ⩽ d_{G}(x_{1}) ⩽ d_{G−I−S} (x_{1}) + |I| + |S| = h + |I| + |S|.

So, |S| ⩾ δ(G) − h − |I|. Combining this with Lemma 2.2, we get

(2.4)  |S| ⩾ δ(G) − h − |I| ⩾ \frac{n(a + b − 1) + b}{a + 2b − 1} − h − |I|.

Claim 1. |I| ⩽ \frac{b(n−1)}{a+2b−1} . Indeed, For arbitrary x ∈ I, we have d_{G}(x) ⩾ δ(G). Since I is independent, we obtain n ⩾ d_{G}(x)+|I| ⩾ δ(G)+|I|, which implies |I| ⩽ n−δ(G). Combining this with Lemma 2.2, we get

|I| ⩽ n − δ(G) ⩽ n − \frac{n(a + b − 1) + b}{a + 2b − 1} = \frac{b(n − 1)}{a + 2b − 1} .

Claim 2. 1 ⩽ h ⩽ a − 1. Assume h = 0 and set λ = |{x : x ∈ T, d_{G−I−S} (x) = 0}|. Then, we have λ ⩾ 1. Let Y = V (G) ∖ (I ∪ S). In view of h = 0 and T ⊂ Y, we get

(2.5)  N_{G}(Y) ≠ V (G).

If |Y | ⩾ ⌊\frac{bn}{a+2b−1} ⌋, then by the assumption of Theorem 2.1 we obtain N_{G}(Y) = V (G), which contradicts (2.5). Therefore, |Y | < ⌊\frac{bn}{a+2b−1} ⌋. Combining this with the condition of Theorem 2.1, we get

n − λ ⩾ |N_{G}(Y)| ⩾ \frac{a + 2b − 1}{b} |Y | = \frac{a + 2b − 1}{b} (n − |I| − |S|),

and then,

(2.6)  |S| ⩾ n − |I| − \frac{b(n − λ)}{a + 2b − 1} = \frac{n(a + b − 1) + bλ}{a + 2b − 1} − |I|.

Using (2.6), 2 ⩽ a ⩽ b, Claim 1, λ ⩾ 1 and the fact that |I| + |S| + |T | ⩽ n, we obtain

−1 ⩾ δ_{H} (S, T) = b|S| + d_{G−I−S} (T) − a|T |

⩾ b|S| + |T | − λ − a|T | = b|S| − (a − 1)|T | − λ

⩾ b|S| − (a − 1)(n − |I| − |S|) − λ

= (a + b − 1)|S| + (a − 1)|I| − (a − 1)n − λ

⩾ (a + b − 1)[ \frac{n(a + b − 1) + bλ}{a + 2b − 1} − |I|] + (a − 1)|I| − (a − 1)n − λ

= \frac{b^{2}n}{a + 2b − 1} − b|I| + \frac{λ(ab + b^{2} − a − 3b + 1)}{a + 2b − 1}

⩾ \frac{b^{2}n}{a + 2b − 1} − \frac{b^{2}(n − 1)}{a + 2b − 1} + \frac{ab + b^{2} − a − 3b + 1}{a + 2b − 1}

= \frac{2b^{2} + ab − 3b − a + 1}{a + 2b − 1} = \frac{(b − 1)(2b − 1) + a(b − 1)}{a + 2b − 1} = b − 1 ⩾ 1 > 0,

a contradiction. So 1 ⩽ h ⩽ a − 1.

Next we shall consider two cases and derive contradictions in each case. Case 1. |N_{G}(T)| < \frac{a+2b−1}{b} |T |. First, we prove the following claim. Claim 3. N_{G}(T) = V (G). Suppose, to the contrary, that N_{G}(T) ≠ V (G). By the assumption of Theorem 2.1, we get |T | < ⌊\frac{bn}{a+2b−1} ⌋. (Or, |T | ⩾ ⌊\frac{bn}{a+2b−1} ⌋ and so N_{G}(T) = V (G), which contradicts N_{G}(T) ≠ V (G).) Since |T | < ⌊\frac{bn}{a+2b−1} ⌋, according to the assumption of Theorem 2.1 we have |N_{G}(T)| ⩾ \frac{a+2b−1}{b} |T |, which contradicts |N_{G}(T)| < \frac{a+2b−1}{b} |T |. Therefore, we obtain N_{G}(T) = V (G).

From Claim 2, we know that 1 ⩽ h ⩽ a − 1. In the following we consider two subcases with h = 1 and 2 ⩽ h ⩽ a − 1. Subcase 1.1. h = 1. According to |N_{G}(T)| < \frac{a+2b−1}{b} |T | and Claim 3, we get

|T | > \frac{b|N_{G}(T)|}{a + 2b − 1} = \frac{bn}{a + 2b − 1} .

Note that ⌊\frac{bn}{a+2b−1} ⌋ ⩽ \frac{bn}{a+2b−1} . Then we have |T | > \frac{bn}{a+2b−1} ⩾ ⌊ \frac{bn}{a+2b−1} ⌋. By the integrity of |T |, we obtain

(2.7)  |T | ⩾ ⌊ \frac{bn}{a + 2b − 1} ⌋ + 1.
From (2.7), T ⊂ V (G) − I − S and d_{G−I−S} (x_{1}) = h = 1, we get
(2.8)  |T ∖ N_{G}(x_{1})| = |T ∖ N_{G−I−S} (x_{1})| ⩾ |T | − 1 ⩾ ⌊ \frac{bn}{a + 2b − 1} ⌋.

In view of (2.8) and the assumption of Theorem 2.1, we have

(2.9)  N_{G}(T ∖ N_{G}(x_{1})) = V (G).

However, it is obvious that x_{1} ∉ N_{G}(T ∖ N_{G}(x_{1})), which contradicts (2.9).

Subcase 1.2. 2 ⩽ h ⩽ a − 1. By N_{G}(T) < \frac{a+2b−1}{b} |T |, Claim 3 and n > 1 + \frac{(a+2b−1)(2a+b−4)}{b} , we have

|T | > \frac{bn}{a + 2b − 1} > \frac{b}{a + 2b − 1} [1 + \frac{(a + 2b − 1)(2a + b − 4)}{b} ] > a − 1 ⩾ h,

and so T ∖ N_{G}(x_{1}) = T ∖ N_{G−I−S} (x_{1}) ≠ ϕ. Obviously, x_{1} ∉ N_{G}(T ∖ N_{G}(x_{1})) and so N_{G}(T ∖ N_{G}(x_{1})) ≠ V (G). Hence, we have |T ∖ N_{G}(x_{1})| < ⌊\frac{bn}{a+2b−1} ⌋(Otherwise, |T ∖N_{G}(x_{1})| ⩾ ⌊\frac{bn}{a+2b−1} ⌋, then from Theorem 2.1 we have N_{G}(T ∖N_{G}(x_{1})) = V (G), a contradiction).

According to the assumption of Theorem 2.1 and T ⊂ V (G) − I − S, we get

n − 1 ⩾ |N_{G}(T ∖ N_{G}(x_{1}))| ⩾ \frac{a + 2b − 1}{b} |T ∖ N_{G}(x_{1})|

= \frac{a + 2b − 1}{b} |T ∖ N_{G−I−S} (x_{1})| ⩾ \frac{a + 2b − 1}{b} (|T | − h),

which implies

(2.10)  |T | ⩽ h + \frac{b(n − 1)}{a + 2b − 1} .

According to Claim 1, (2.3), (2.4) and (2.10), we have

−1 ⩾ δ_{H} (S, T) = b|S| + d_{G−I−S} (T) − a|T |

⩾ b|S| + h|T | − a|T | = b|S| − (a − h)|T |

⩾ b[ \frac{n(a + b − 1) + b}{a + 2b − 1} − h − |I|] − (a − h)[h + \frac{b(n − 1)}{a + 2b − 1} ]

⩾ b[ \frac{n(a + b − 1) + b}{a + 2b − 1} − h − \frac{b(n − 1)}{a + 2b − 1} ] − (a − h)[h + \frac{b(n − 1)}{a + 2b − 1} ]

= h^{2} − h[a + b − \frac{b(n − 1)}{a + 2b − 1} ] + \frac{b(a + 2b − n)}{a + 2b − 1} ,

that is,

(2.11)  − 1 ⩾ δ_{H} (S, T) ⩾ h^{2} − h[a + b − \frac{b(n − 1)}{a + 2b − 1} ] + \frac{b(a + 2b − n)}{a + 2b − 1} .

Set

f(h) = h^{2} − h[a + b − \frac{b(n − 1)}{a + 2b − 1} ] + \frac{b(a + 2b − n)}{a + 2b − 1} .

Then by 2 ⩽ h ⩽ a − 1, n > 1 + \frac{(a+2b−1)(2a+b−4)}{b} and a ⩾ 2, we obtain

f′(h) = 2h−[a+b−\frac{b(n − 1)}{a + 2b − 1} ] ⩾ 4−a−b+\frac{b(n − 1)}{a + 2b − 1} ⩾ 4−a−b+2a+b−4 = a ⩾ 2.

It is obvious that the function f(h) attains its minimum value at h = 2, since 2 ⩽ h ⩽ a − 1. Thus, by (2.11), we have

−1 ⩾ δ_{H} (S, T) ⩾ f(h) ⩾ f(2)

= 4 − 2(a + b) + \frac{2b(n − 1)}{a + 2b − 1} + \frac{b(a + 2b − n)}{a + 2b − 1}

= 4 − 2(a + b) + \frac{2b(n − 1)}{a + 2b − 1} + \frac{b(a + 2b − 1) − b(n − 1)}{a + 2b − 1}

= 4 − 2(a + b) + b + \frac{b(n − 1)}{a + 2b − 1}

⩾ 4 − 2(a + b) + b + 2a + b − 4 = 0,

a contradiction. Case 2. |N_{G}(T)| ⩾ \frac{a+2b−1}{b} |T |. In this case, we have

(2.12)  |T | ⩽ \frac{b}{a + 2b − 1} |N_{G}(T)| ⩽ \frac{bn}{a + 2b − 1} .

Subcase 2.1. h = 1. Subsubcase 2.1.1. |T | > \frac{b(n−1)}{a+2b−1} . From (2.4) and h = 1, we get

(2.13)  |S| + |I| + |T | > \frac{n(a + b − 1) + b}{a + 2b − 1} − 1 + \frac{b(n − 1)}{a + 2b − 1} = n − 1.

On the other hand, |S| + |I| + |T | ⩽ n. Combining this with (2.13), we get

(2.14)  |S| + |I| + |T | = n.

Using Claim 1, (2.12) and (2.14), we have

δ_{H} (S, T)= b|S| + d_{G−I−S} (T) − a(T)

= b(n − |I| − |T |) + d_{G−I−S} (T) − a|T |

⩾ b(n − |I| − |T |) + |T | − a|T | = b(n − |I|) − (a + b − 1)|T |

⩾ b[n − \frac{b(n − 1)}{a + 2b − 1} ] − (a + b − 1) · \frac{bn}{a + 2b − 1}

= \frac{b^{2}}{a + 2b − 1} > 0,

which contradicts (2.3). Subsubcase 2.1.2. |T | ⩽ \frac{b(n−1)}{a+2b−1} . We write m = |\{x : x ∈ T, d_{G−I−S} (x) = 1\}|. Clearly, |T | ⩾ m. In view of (2.3), (2.4), Claim 1, h = 1, |T | ⩽ \frac{b(n−1)}{a+2b−1} and |T | ⩾ m, we get

−1 ⩾ δ_{H} (S, T) = b|S| + d_{G−I−S} (T) − a|T |

⩾ b|S| + 2|T | − m − a|T | = b|S| − (a − 2)|T | − m

⩾ b[ \frac{n(a + b − 1) + b}{a + 2b − 1} − 1 − |I|] − (a − 2) · \frac{b(n − 1)}{a + 2b − 1} − m

⩾ b[ \frac{n(a + b − 1) + b}{a + 2b − 1} − 1 − \frac{b(n − 1)}{a + 2b − 1} ] − (a − 2) · \frac{b(n − 1)}{a + 2b − 1} − m

= \frac{b(n − 1)}{a + 2b − 1} − m ⩾ |T | − m ⩾ 0,

a contradiction.

Subcase 2.2. 2 ⩽ h ⩽ a − 1. According to (2.4), (2.12) and Claim 1, n > 1 + \frac{(a+2b−1)(2a+b−4)}{b} and h ⩾ 2, we have

δ_{H} (S, T)= b|S| + d_{G−I−S} (T) − a|T |

⩾ b[n − \frac{b(n − 1)}{a + 2b − 1} − |I| − h] + h|T | − a|T |

⩾ b[n − \frac{2b(n − 1)}{a + 2b − 1} − h] − \frac{bn(a − h)}{a + 2b − 1}

= bn − \frac{2b^{2}(n − 1)}{a + 2b − 1} − \frac{bn(a − h)}{a + 2b − 1} − bh

= bn − \frac{2b^{2}(n − 1)}{a + 2b − 1} − \frac{b(a − h)(n − 1)}{a + 2b − 1} − \frac{b(a − h)}{a + 2b − 1} − bh

= bn − \frac{2b^{2}(n − 1)}{a + 2b − 1} − \frac{ab(n − 1)}{a + 2b − 1} + \frac{bh(n − 1)}{a + 2b − 1} − \frac{b(a − h)}{a + 2b − 1} − bh

= bn − (n − 1) · \frac{b(a + 2b)}{a + 2b − 1} + h[ \frac{b(n − 1)}{a + 2b − 1} − b] − \frac{b(a − h)}{a + 2b − 1}

⩾ bn − (n − 1) · \frac{b(a + 2b)}{a + 2b − 1} + 2[ \frac{b(n − 1)}{a + 2b − 1} − b] − \frac{b(a − 2)}{a + 2b − 1}

= b(n − 1) − b + \frac{b(n − 1)(2 − a − 2b)}{a + 2b − 1} − \frac{b(a − 2)}{a + 2b − 1}

= b(n − 1)( 1 − \frac{a + 2b − 2}{a + 2b − 1} ) − b − \frac{b(a − 2)}{a + 2b − 1}

⩾ \frac{(a + 2b − 1)(2a + b − 4) − b(a + 2b − 1) − b(a − 2)}{a + 2b − 1}

= \frac{(a − 2)(2a + 3b − 2)}{a + 2b − 1} ⩾ 0,

which contradicts (2.3).

Now, we deduce the contradictions. Therefore, H has a fractional [a, b]-factor. That is, G is fractional ID-[a, b]-factor-critical. □

Acknowledgments. The authors would like to thank the referees for valuable comments. This work is supported by the National Natural Science Foundation of China No. 11371052 and the 111 Project of China.

References

1. J. A. Bondy, U. S. R. Murty, Graph Theory, 2nd ed., Springer, New York, 2008.

2. P. Katerinis, Toughness of graphs and the existence of factors, Discrete Math. 80 (1990), 81–92.

3. M. Kano, A sufficient condition for a graph to have [a, b]-factors, Graphs Comb. 6 (1990), 245–251.

4. Y. Li, M. Cai, A degree condition for a graph to have [a, b]-factors, J. Graph Theory 27 (1998), 1–6.

5. G. Liu, L. Zhang, Fractional (g, f)-factors of graphs, Acta Math. Sci., Ser. B, Engl. Ed. 21 (2001), 541–545.

6. H. Matsuda, Fan-type results for the existence of [a, b]-factors, Discrete Math. 306 (2006), 688–693.

7. Y. Nam, Binding numbers and connected factors, Graphs Comb. 26 (2010), 805–813.

8. S. Zhou, Binding numbers and [a, b]-factors excluding a given k-factor, C. R., Math., Acad. Sci. Paris 349(19–20) (2011), 1021–1024.

9. S. Zhou, B. Pu, Y. Xu, Neighbourhood and the existence of fractional k-factors of graphs, Bull. Aust. Math. Soc. 81 (2010), 473–480.

10. S. Zhou, Z. Sun, Neighbourhood conditions for fractional ID-k-factor-critical graphs, Acta Math. Appl. Sin., Engl. Ser., to appear.

11. S. Zhou, H. Liu, Neighbourhood conditions and fractional k-factors, Bull. Malays. Math. Sci. Soc. (2) 32 (2009), 37–45.

12. S. Zhou, L. Xu, Z. Sun, Independence number and minimum degree for fractional ID-k-factor-critical graphs, Aequationes Math. 84 (2012), 71–76.

13. S. Zhou, Z. Sun, H. Liu, A minimum degree condition for fractional ID-[a, b]-factor-critical graphs, Bull. Aust. Math. Soc. 86 (2012), 177–183.

Department of Mathematics (Received 16 03 2014) Beijing Jiaotong University Beijing P. R. China

kuailenanshi@126.com

School of Mathematical Science Nanjing Normal University Nanjing P. R. China

zrsun@njnu.edu.cn