An existence theorem on fractional ID-(g, f)-factor-critical covered graphs

Abstract

A fractional (g, f)-factor of a graph G is a function h that assigns to each edge of G a number in [0,1] so that, for each vertex x of G we admit $g(x)\le d_G^h(x)\le f(x),$ where $d_G^h(x)=\sum _{e\ni x}h(e).$ A graph G is called a fractional (g, f)-covered graph if for any $e\in E(G),$ G admits a fractional (g, f)-factor h satisfying h(e) = 1. A graph G is called a fractional ID-(g, f)-factor-critical covered graph if for any independent set I of G, G – I is a fractional (g, f)-covered graph. In this paper, we present a neighborhood of independent set and minimum degree condition for a graph to be a fractional ID-(g, f)-factor-critical covered graph. Furthermore, we show that the main result is best possible in some sense.

Keywords:

• Neighborhood of independent set
• minimum degree
• fractional (g
• f)-factor
• fractional (g
• f)-covered graph
• fractional ID-(g
• f)-factor-critical covered graph

2020 Mathematics Subject Classification:

• 05C70

1. Introduction

In this paper, we consider only finite, undirected and simple graphs. Let G be a graph. We use V(G) to denote the vertex set of G, and use E(G) to denote the edge set of G. For any $x\in V(G),$ we denote by $N_G(x)$ the set of vertices adjacent to x in G, and $d_G(x)=|N_G(x)|$ is the degree of x in G. We use $\delta (G)$ to denote the minimum degree of G, namely, $\delta (G)=\min \{d_G(x):x\in V(G)\}.$ Let X be a vertex subset of G. We use $G[X]$ to denote the subgraph of G induced by X, use G – X to denote the subgraph derived from G by removing vertices in X together with the edges incident to vertices in X, and write $N_G(X)=\underset{x\in X}{\cup }{N}_G(x).$ A vertex subset X of G is independent if no two vertices of X are adjacent.

Let a and b be two nonnegative integers with $a\le b.$ Let g and f be two nonnegative integer-valued functions defined on V(G) satisfying $g(x)\le f(x)$ for every $x\in V(G).$ Then a (g, f)-factor of G is a spanning subgraph F of G satisfying $g(x)\le d_F(x)\le f(x)$ for every $x\in V(G).$ If g(x) = a and f(x) = b for all $x\in V(G),$ then a (g, f)-factor is called an $[a,b]$-factor. A fractional (g, f)-factor of G is a function h that assigns to each edge of G a number in [0,1] so that, for each vertex x of G we admit $g(x)\le d_G^h(x)\le f(x),$ where $d_G^h(x)=\sum _{e\ni x}h(e).$ If $g(x)=f(x)$ for every $x\in V(G),$ then a fractional (g, f)-factor is called a fractional f-factor. If g(x) = a and f(x) = b for each $x\in V(G),$ then a fractional (g, f)-factor is called a fractional $[a,b]$-factor. A fractional $[k,k]$-factor is simply called a fractional k-factor.

A graph G is called a fractional (g, f)-covered graph if for any $e\in E(G),$ G admits a fractional (g, f)-factor h satisfying h(e) = 1. If g(x) = a and f(x) = b for any $x\in V(G),$ then a fractional (g, f)-covered graph is called a fractional $[a,b]$-covered graph. A fractional $[k,k]$-covered graph is simply called a fractional k-covered graph.

A graph G is called a fractional ID-(g, f)-factor-critical graph if for any independent set I of G, G – I admits a fractional (g, f)-factor. If g(x) = a and f(x) = b for all $x\in V(G),$ then a fractional ID-(g, f)-factor-critical graph is called a fractional ID-$[a,b]$-factor-critical graph. A fractional ID-$[k,k]$-factor-critical graph is simply called a fractional ID-k-factor-critical graph.

A graph G is called a fractional ID-(g, f)-factor-critical covered graph if for any independent set I of G, G – I is a fractional (g, f)-covered graph. If g(x) = a and f(x) = b for every $x\in V(G),$ then a fractional ID-(g, f)-factor-critical covered graph is called a fractional ID-$[a,b]$-factor-critical covered graph. A fractional ID-$[k,k]$-factor-critical covered graph is simply called a fractional ID-k-factor-critical covered graph.

Aldred, Fujisawa and Saito [1], Ferrara et al. [4] derived some results for graphs to admit 2-factors. Shiu and Liu [12] investigated the existence of k-factors in regular graphs. Kano et al. [6], Zhou [22], Zhou et al. [24], Zhou et al. [23], Zhou et al. [25] studied [1, 2]-factors of graphs, and got some sufficient conditions for graphs to possess [1, 2]-factors. Matsuda [11] showed a neighborhood condition for the existence of $[a,b]$-factors in graphs. Egawa and Kano [3] obtained some sufficient conditions for graphs to have (g, f)-factors. Zhou et al. [29], Wang and Zhang [13] investigated the existence of edge-disjoint factors in graphs. Liu and Zhang [9], Katerinis [7] presented some sufficient conditions for graphs to have fractional k-factors. Cai et al. [2] discussed the existence of fractional f-factors in random graphs. Zhou et al. [27], Zhou [19, 20], Wang and Zhang [15], Yuan and Hao [18] posed some sufficient conditions for the existences of fractional $[a,b]$-factors in graphs. Lv [10], Wang and Zhang [14] got some results for graphs to admit fractional (g, f)-factors. Zhou [21], Zhou et al. [26] studied restricted fractional (g, f)-factors of graphs and derived some results for graphs to possess restricted fractional (g, f)-factors. Yuan and Hao [16] gave a degree condition for the existence of fractional $[a,b]$-covered graphs. Zhou et al. [28] established a relationship between neighborhood of independent set and fractional ID-k-factor-critical graph. Yuan and Hao [17] studied the existence of fractional ID-$[a,b]$-factor-critical graphs. Jiang [5] showed a sufficient condition for graphs to be fractional ID-$[a,b]$-factor-critical covered graphs. In this article, we investigate fractional ID-(g, f)-factor-critical covered graphs and derive an existence theorem of fractional ID-(g, f)-factor-critical covered graphs, which is shown in the following.

Theorem 1.

Let a, b and d be three nonnegative integers with $b-d\ge a\ge 2$, let G be a graph of order p satisfying $p\ge \frac{(a+b-4)(2a+b+d)+6}{a+d}$, and let g and f be two integer-valued functions defined on V(G) with $a\le g(x)\le f(x)-d\le b-d$ for any $x\in V(G)$. If $$\delta (G)\ge \frac{(a+b-1)p+a+b+1}{2a+b+d-1},$$ and $$|N_G(X)|\ge \frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|X\right|-a-d+1}{2a+b+d-1}$$ for every non-empty independent subset X of V(G), then G is a fractional ID-(g, f)-factor-critical covered graph.

We easily obtain the following corollary by setting d = 0 in Theorem 1.

Corollary 1.

Let a, b be two nonnegative integers with $b\ge a\ge 2$, let G be a graph of order p satisfying $p\ge \frac{(2a+b)(a+b-4)+6}{a}$, and let g and f be two integer-valued functions defined on V(G) with $a\le g(x)\le f(x)\le b$ for any $x\in V(G)$. If $$\delta (G)\ge \frac{(a+b-1)p+a+b+1}{2a+b-1},$$ and $$|N_G(X)|\ge \frac{(a+b-1)p+\frac{2a+b-1}{a+b-1}\left|X\right|-a+1}{2a+b-1}$$ for every non-empty independent subset X of V(G), then G is a fractional ID-(g, f)-factor-critical covered graph.

If a = b = k in Corollary 1, then we have the following corollary.

Corollary 2.

Let k be a nonnegative integer with $k\ge 2$, let G be a graph of order p satisfying $p\ge 6k-12+\frac{6}{k}$. If $$\delta (G)\ge \frac{(2k-1)p+2k+1}{3k-1},$$ and $$|N_G(X)|\ge \frac{(2k-1)p+\frac{3k-1}{2k-1}\left|X\right|-k+1}{3k-1}$$ for every non-empty independent subset X of V(G), then G is a fractional ID-k-factor-critical covered graph.

2. Proof of Theorem 1

We first introduce the following theorem, which plays a key role to the proof of Theorem 1.

Theorem 2

([8]). Let G be a graph, and let g and f be two nonnegative integer-valued functions defined on V(G) satisfying $g(x)\le f(x)$ for any $x\in V(G)$. Then G is fractional (g, f)-covered if and only if $${\gamma }_G(X,Y)=f(X)+d_{G-X}(Y)-g(Y)\ge \epsilon (X)$$ for all $X\subseteq V(G)$ and $Y=\{x:x\in V(G)\setminus X,d_{G-X}(x)\le g(x)\}$, where $\epsilon (X)$ is defined by $$\epsilon (X)=\{\begin{array}{cc}2,\hfill & ifXis\mathit{not}\mathit{independent},\hfill \\ 1,\hfill & ifXis\mathit{independent}\mathit{and}\mathit{there}isan\mathit{edge}\mathit{joining}\hfill \\ \hfill & X\mathit{and}V(G)\setminus (X\cup Y),or\mathit{there}isan\mathit{edge}e=xy\hfill \\ \hfill & \mathit{joining}X\mathit{and}Y\mathit{with}{d}_{G-X}(y)=g(y)\mathit{for}y\in Y,\hfill \\ 0,\hfill & \mathit{otherwise}.\hfill \end{array}$$

Proof of Theorem 1.

For any independent set I of G, we write $H=G-I.$ It suffices to verify that H is a fractional (g, f)-covered graph. Suppose, to the contrary, that H is not a fractional (g, f)-covered graph. Then it follows from Theorem 2 that (1) $${\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\le \epsilon (X)-1$$(1) for some vertex subset X of H, where $Y=\{x:x\in V(H)\setminus X,d_{H-X}(x)\le g(x)\}.$

Claim 1. $Y\ne \varnothing .$

Proof.

Assume that $Y=\varnothing .$ Note that $\epsilon (X)\le \left|X\right|$ by the definition of $\epsilon (X).$ Combining this with (1), we obtain $$\epsilon (X)-1\ge {\gamma }_H(X,\varnothing )=f(X)\ge (a+d)\left|X\right|\ge \left|X\right|\ge \epsilon (X),$$ which is a contradiction. Hence, $Y\ne \varnothing .$ This completes the proof of Claim 1. □

Using Claim 1, we know $Y\ne \varnothing ,$ and so we may define $$h=\min \{d_{H-X}(x):x\in Y\}.$$

Obviously, it follows from the definition of Y that $0\le h\le b-d.$

Claim 2. $\left|X\right|\ge \delta (G)-\left|I\right|-h.$

Proof.

By examining a vertex of Y, we find that it can possess neighbors in X, I and at most h additional neighbors. Hence, we derive the following bound on $\delta (G),$ namely, $\delta (G)\le \left|X\right|+\left|I\right|+h.$ Thus, we have $$\left|X\right|\ge \delta (G)-\left|I\right|-h.$$

We finish the proof of Claim 2. □

In what follows, we shall consider three cases by the value of h and deduce a contradiction in each case.

Case 1.

h = 0.

Let $T=\{x:x\in Y,d_{H-X}(x)=0\}.$ Then we easily see that $T\ne \varnothing$ and T is an independent set of G. Thus, we admit (2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) and (3) $$|N_G(T)|\ge \frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|T\right|-a-d+1}{2a+b+d-1}.$$(3)

According to (1)(1) $${\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\le \epsilon (X)-1$$(1) , (2)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) , $\epsilon (X)\le 2,\left|I\right|\le p-\delta (G)$ (Since I is an independent set), $\left|X\right|+\left|Y\right|+\left|I\right|\le p$ and $\delta (G)\ge \frac{(a+b-1)n+a+b+1}{2a+b+d-1},$ we get $$\begin{array}{c}1\ge \epsilon (X)-1\ge {\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\\ \ge (a+d)\left|X\right|+\left|Y\right|-\left|T\right|-(b-d)\left|Y\right|\\ =(a+d)\left|X\right|-(b-d-1)\left|Y\right|-\left|T\right|\\ \ge (a+d)\left|X\right|-(b-d-1)(p-|X|-|I|)-\left|T\right|\\ =-(b-d-1)p+(a+b-1)\left|X\right|+(b-d-1)\left|I\right|-\left|T\right|\\ \ge -(b-d-1)p+(a+b-1)(|N_G(T)|-|I|)+(b-d-1)\left|I\right|-\left|T\right|\\ =-(b-d-1)p+(a+b-1)|N_G(T)|-(a+d)\left|I\right|-\left|T\right|\\ \ge -(b-d-1)p+(a+b-1)|N_G(T)|-(a+d)(p-\delta (G))-\left|T\right|\\ =-(a+b-1)p+(a+b-1)|N_G(T)|+(a+d)\delta (G)-\left|T\right|\\ \ge -(a+b-1)p+(a+b-1)|N_G(T)|+(a+d)·\frac{(a+b-1)p+a+b+1}{2a+b+d-1}-\left|T\right|,\end{array}$$ which implies $$\begin{array}{c}|N_G(T)|\le \frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|T\right|-a-d+\frac{b-d-1}{a+b-1}}{2a+b+d-1}\\ <\frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|T\right|-a-d+1}{2a+b+d-1},\end{array}$$ which contradicts (3)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) .

Case 2.

h = 1.

In terms of Claim 2, $\epsilon (X)\le 2,\left|I\right|\le p-\delta (G),\left|X\right|+\left|Y\right|+\left|I\right|\le p$ and $\delta (G)\ge \frac{(a+b-1)n+a+b+1}{2a+b+d-1},$ we admit $$\begin{array}{c}{\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\\ \ge (a+d)\left|X\right|+\left|Y\right|-(b-d)\left|Y\right|\\ =(a+d)\left|X\right|-(b-d-1)\left|Y\right|\\ \ge (a+d)\left|X\right|-(b-d-1)(p-|X|-|I|)\\ =(a+b-1)\left|X\right|-(b-d-1)p+(b-d-1)\left|I\right|\\ \ge (a+b-1)(\delta (G)-|I|-1)-(b-d-1)p+(b-d-1)\left|I\right|\\ =(a+b-1)\delta (G)-(a+d)\left|I\right|-(b-d-1)p-(a+b-1)\\ \ge (a+b-1)\delta (G)-(a+d)(p-\delta (G))-(b-d-1)p-(a+b-1)\\ =(2a+b+d-1)\delta (G)-(a+b-1)p-(a+b-1)\\ \ge (2a+b+d-1)·\frac{(a+b-1)n+a+b+1}{2a+b+d-1}-(a+b-1)p-(a+b-1)\\ =2\ge \epsilon (X),\end{array}$$ which contradicts (1)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) .

Case 3.

$2\le h\le b-d.$

According to (1)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) , Claim 2, $\epsilon (X)\le 2,\left|I\right|\le p-\delta (G)$ and $\left|X\right|+\left|Y\right|+\left|I\right|\le p,$ we derive $$\begin{array}{c}1\ge \epsilon (X)-1\ge {\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\\ \ge (a+d)\left|X\right|+h\left|Y\right|-(b-d)\left|Y\right|\\ =(a+d)\left|X\right|-(b-d-h)\left|Y\right|\\ \ge (a+d)\left|X\right|-(b-d-h)(p-|X|-|I|)\\ =(a+b-h)\left|X\right|+(b-d-h)\left|I\right|-(b-d-h)p\\ \ge (a+b-h)(\delta (G)-|I|-h)+(b-d-h)\left|I\right|-(b-d-h)p\\ =(a+b-h)\delta (G)-(a+d)\left|I\right|-(a+b-h)h-(b-d-h)p\\ \ge (a+b-h)\delta (G)-(a+d)(p-\delta (G))-(a+b-h)h-(b-d-h)p\\ =(2a+b+d-h)\delta (G)-(a+b-h)h-(a+b-h)p,\end{array}$$ which implies (4) $$\delta (G)\le \frac{(a+b-h)p+(a+b-h)h+1}{2a+b+d-h}.$$(4)

Let $\phi (h)=\frac{(a+b-h)p+(a+b-h)h+1}{2a+b+d-h}.$ Then it follows from $2\le h\le b-d$ and $p\ge \frac{(a+b-4)(2a+b+d)+6}{a+d}$ that $$\begin{array}{c}\phi \prime (h)=\frac{(-p+a+b-2h)(2a+b+d-h)+(a+b-h)p+(a+b-h)h+1}{{(2a+b+d-h)}^2}\\ =\frac{-(a+d)p+(a+b-2h)(2a+b+d)+h^2+1}{{(2a+b+d-h)}^2}\\ \le \frac{-(a+d)p+(a+b-4)(2a+b+d)+5}{{(2a+b+d-h)}^2}\\ <0,\end{array}$$ which implies that $\phi (h)$ attains its maximum value at h = 2. Combining this with (4)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) , we admit (5) $$\delta (G)\le \phi (h)\le \phi (2)=\frac{(a+b-2)p+2(a+b-2)+1}{2a+b+d-2}.$$(5)

Claim 3. $\frac{(a+b-2)p+2(a+b-2)+1}{2a+b+d-2}<\frac{(a+b-1)p+a+b+1}{2a+b+d-1}.$

Proof.

Let $A=\frac{(a+b-2)p+2(a+b-2)+1}{2a+b+d-2}$ and $B=\frac{(a+b-1)p+a+b+1}{2a+b+d-1}.$ Then by $p\ge \frac{(a+b-4)(2a+b+d)+6}{a+d}$ we derive $$\begin{array}{c}(2a+b+d-2)(2a+b+d-1)(A-B)\\ =(2a+b+d-1)((a+b-2)p+2(a+b-2)+1)-(2a+b+d-2)((a+b-1)p+a+b+1)\\ =-(a+d)p+(a+b-4)(2a+b+d)+5\\ \le -1<0,\end{array}$$

which implies A < B, that is, $\frac{(a+b-2)p+2(a+b-2)+1}{2a+b+d-2}<\frac{(a+b-1)p+a+b+1}{2a+b+d-1}.$ This completes the proof of Claim 3. □

It follows from (5)(2) $$|N_G(T)|\le \left|X\right|+\left|I\right|$$(2) and Claim 3 that $$\delta (G)<\frac{(a+b-1)p+a+b+1}{2a+b+d-1},$$

which contradicts that $\delta (G)\ge \frac{(a+b-1)p+a+b+1}{2a+b+d-1}.$ Theorem 1 is proved. □

3. Remark

Now, we show that $$\delta (G)\ge \frac{(a+b-1)p+a+b+1}{2a+b+d-1},$$ and $$|N_G(X)|\ge \frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|X\right|-a-d+1}{2a+b+d-1}$$ for every non-empty independent subset X of V(G) in Theorem 1 cannot be replaced by $$\delta (G)\ge \frac{(a+b-1)p+a+b+1}{2a+b+d-1}-1,$$

and $$|N_G(X)|\ge \frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|X\right|-a-d+1}{2a+b+d-1}-1$$ for every non-empty independent subset X of V(G).

Let a, b and d be three nonnegative integers such that $2\le a=b-d$ and $\frac{(b-d)(a+b-1)}{a+d}$ is an integer. We can explain this above problem by constructing a graph $G=K_{\frac{(b-d)(a+b-1)}{a+d}}\vee ((a+b-1)K_1\vee (a+b-1)K_1).$ Let $Q=V((a+b-1)K_1).$ Thus, we have $$\begin{array}{c}p=|V(G)|=\frac{(b-d)(a+b-1)}{a+d}+2(a+b-1)\\ =\frac{(a+b-1)(2a+b+d)}{a+d}\\ >\frac{(a+b-4)(2a+b+d)+6}{a+d},\\ \delta (G)=\frac{(b-d)(a+b-1)}{a+d}+a+b-1\\ =\frac{(a+b-1)p+a+b-1}{2a+b+d-1},\end{array}$$ and $$\begin{array}{c}|N_G(Q)|=\frac{(b-d)(a+b-1)}{a+d}+a+b-1\\ =\frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|Q\right|-a-d}{2a+b+d-1}.\end{array}$$

Furthermore, we easily see that $$\frac{(a+b-1)p+a+b+1}{2a+b+d-1}-1<\delta (G)<\frac{(a+b-1)p+a+b+1}{2a+b+d-1},$$

and $$\frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|X\right|-a-d+1}{2a+b+d-1}-1<|N_G(X)|<\frac{(a+b-1)p+\frac{2a+b+d-1}{a+b-1}\left|X\right|-a-d+1}{2a+b+d-1}$$ for every non-empty independent subset X of G.

Let g and f be two nonnegative integer-valued functions defined on V(G) with g(x) = a and f(x) = b for each $x\in V(G).$ Write $I=V((a+b-1)K_1),H=G-I,X=V(K_{\frac{(b-d)(a+b-1)}{a+d}})$ and $Y=V((a+b-1)K_1).$ Obviously, I is an independent set of G, $\left|X\right|=\frac{(b-d)(a+b-1)}{a+d},\left|Y\right|=a+b-1,d_{H-X}(Y)=0$ and $\epsilon (X)=2.$ Thus, we get $$\begin{array}{c}{\gamma }_H(X,Y)=f(X)+d_{H-X}(Y)-g(Y)\\ =b\left|X\right|-a\left|Y\right|\\ =b·\frac{(b-d)(a+b-1)}{a+d}-a(a+b-1)\\ =b·\frac{a(a+b-1)}{b}-a(a+b-1)\\ =0<2=\epsilon (X).\end{array}$$

According to Theorem 2, H is not a fractional (g, f)-covered graph, and so G is not a fractional ID-(g, f)-factor-critical covered graph.

Acknowledgments

I would like to thank the referees for their constructive comments which resulted in the improvements to the first version of the paper.