Menu
Zhou, Xu and Sun [S. Zhou, Y. Xu, Z. Sun, Degree conditions for fractional \((a,b,k)\)-critical covered graphs, Information Processing Letters 152(2019)105838] defined the concept of a fractional \((a,b,k)\)-critical covered graph, namely, a graph \(G\) is a fractional \((a,b,k)\)-critical covered graph if after removing any \(k\) vertices of \(G\), the remaining graph of \(G\) is a fractional \([a,b]\)-covered graph. In this paper, we prove that a graph \(G\) with \(\delta(G)\geq2+k\) is fractional \((2,b,k)\)-critical covered if \(bind(G)>\frac{b+k}{b-1}\), where \(k\geq0\) and \(b\geq2+k\) are two integers.
All graphs discussed here are finite, undirected and simple. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). For every \(x\in V(G)\), we use \(d_G(x)\) to denote the degree of \(x\) in \(G\), and let \(N_G(x)\) denote the neighborhood of \(x\) in \(G\). Let \(X\) be a subset of \(V(G)\). We write \(N_G(X)=\bigcup\limits_{x\in X}{N_G(x)}\), and write \(G[X]\) for the subgraph of \(G\) induced by \(X\). Define \(G-X=G[V(G)\setminus X]\). A subset \(X\subseteq V(G)\) is called independent if \(G[X]\) does not admit edges. The minimum degree of \(G\) is denoted by \(\delta(G)\), the number of isolated vertices in \(G\) is denoted by \(i(G)\), and the complete graph of order \(n\) is denoted by \(K_n\). The binding number of \(G\) is defined by Woodall [1] as \[bind(G)=\min\left\{\frac{|N_G(X)|}{|X|}:\emptyset\neq X\subseteq V(G), N_G(X)\neq V(G)\right\}.\]
Let \(a,b\) and \(k\) be three nonnegative integers with \(a\leq b\). Then a spanning subgraph \(F\) of \(G\) is called an \([a,b]\)-factor of \(G\) if \(a\leq d_F(x)\leq b\) holds for every \(x\in V(G)\). Let \(h\) be a function from \(E(G)\) to \([0,1]\). Then we call \(G[F_h]\) a fractional \([a,b]\)-factor of \(G\) with an indicator function \(h\) if \(a\leq\sum\limits_{e\ni x}{h(e)}\leq b\) for all \(x\in V(G)\), where \(F_h=\{e: e\in E(G), h(e)>0\}\). In particular, when \(a=b=r\), a fractional \([a,b]\)-factor is a fractional \(r\)-factor. A fractional \([a,b]\)-factor is just an \([a,b]\)-factor if \(h(e)\in\{0,1\}\) for each \(e\in E(G)\). A graph \(G\) is a fractional \([a,b]\)-covered graph if for any \(e\in E(G)\), there exists a fractional \([a,b]\)-factor \(G[F_h]\) such that \(h(e)=1\). In particular, when \(a=b=r\), a fractional \([a,b]\)-covered graph is a fractional \(r\)-covered graph. A graph \(G\) is a fractional \((a,b,k)\)-critical covered graph if after removing any \(k\) vertices of \(G\), the remaining graph of \(G\) is a fractional \([a,b]\)-covered graph. In particular, when \(a=b=r\), a fractional \((a,b,k)\)-critical covered graph is a fractional \((r,k)\)-critical covered graph.
Many scholars studied the problems of factors of graphs and fractional factors of graphs. Zhou, Xu and Sun [2] derived a degree condition for the existence of fractional \((a,b,k)\)-critical covered graphs. Zhou [3] presented a neighborhood union condition for a graph being a fractional \((a,b,k)\)-critical covered graph. In this paper, we study the fractional \((2,b,k)\)-critical covered graph problem, and get a result on fractional \((2,b,k)\)-critical covered graphs which is the following theorem.
Theorem 1. Let \(k\geq0\) and \(b\geq2+k\) be two integers, and let \(G\) be a graph with \(\delta(G)\geq2+k\). If \[bind(G)>\frac{b+k}{b-1},\] then \(G\) is fractional \((2,b,k)\)-critical covered.
We immediately get the following corollary by setting \(k=0\) in Theorem 1.
Corollary 1. Let \(b\geq2\) be an integer, and let \(G\) be a graph with \(\delta(G)\geq2\). If \[bind(G)>\frac{b}{b-1},\] then \(G\) is fractional \([2,b]\)-covered.
We promptly obtain the following corollary if \(b=2\) in Corollary 1.
Corollary 2. Let \(G\) be a graph with \(\delta(G)\geq2\). If \[bind(G)>2,\] then \(G\) is fractional \(2\)-covered.
We begin this section with one definition. For any \(X\subseteq V(G)\) and \(Y=\{x:x\in V(G)\setminus X, d_{G-X}(x)\leq a\}\), we define \(\varepsilon(X,Y)\) as follows: \[\varepsilon(X,Y)=\left\{ \begin{array}{ll} 2,&\text{if} \ X \ \text{is not independent,}\\ 1,&\text{if} \ X \ \text{is independent and there is an edge joining}\\ &X \ \text{and} \ V(G)\setminus(X\cup Y), \ \text{or there is an edge} \ e=xy\\ &\text{joining} \ X \ \text{and} \ Y \ \text{such that} \ d_{G-X}(y)=a \ \text{for} \ y\in Y,\\ 0,&\text{otherwise.}\\ \end{array} \right.\]
Li, Yan and Zhang [4] posed a necessary and sufficient condition for a graph to be a fractional \([a,b]\)-covered graph, which is a special case of Li, Yan and Zhang’s fractional \((g,f)\)-covered graph theorem.
Theorem 2. ([4]) Let \(b\geq a\geq0\) be two integers. Then a graph \(G\) is a fractional \([a,b]\)-covered graph if and only if for any \(X\subseteq V(G)\), \[a|Y|-d_{G-X}(Y)\leq b|X|-\varepsilon(X,Y),\] where \(Y=\{x:x\in V(G)\setminus X, d_{G-X}(x)\leq a\}\).
The proof of Theorem 1 depends heavily on the following theorem, which is equivalent to Theorem 2.
Theorem 3. ([4]) Let \(b\geq a\geq0\) be two integers. Then a graph \(G\) is a fractional \([a,b]\)-covered graph if and only if for any \(X\subseteq V(G)\), \[\sum\limits_{j=0}^{a-1}(a-j)p_j(G-X)\leq b|X|-\varepsilon(X,Y),\] where \(Y=\{x:x\in V(G)\setminus X, d_{G-X}(x)\leq a\}\) and \(p_j(G-X)\) denotes the number of vertices in \(G-X\) with degree \(j\).
Proof of Theorem 1. Let \(Q\subseteq V(G)\) with \(|Q|=k\), and let \(H=G-Q\). It suffices to verify that \(H\) is a fractional \([2,b]\)-covered graph. Suppose, to the contrary, that \(H\) is not a fractional \([2,b]\)-covered graph. Then it follows from Theorem 3 that \[\label{e1} 2p_0(H-X)+p_1(H-X)\geq b|X|-\varepsilon(X,Y)+1\tag{1}\] for some \(X\subseteq V(H)\), where \(Y=\{x:x\in V(H)\setminus X, d_{H-X}(x)\leq2\}\).
We write \(Y_0=\{x:x\in V(H)\setminus X, d_{H-X}(x)=0\}\) and \(Y_1=\{x:x\in V(H)\setminus X, d_{H-X}(x)=1\}\). Obviously, we obtain \(|Y_0|=p_0(H-X)=i(H-X)\) and \(|Y_1|=p_1(H-X)\). The following proof will be divided into three cases.
Case 1. \(Y_1=\emptyset\).
Clearly, \(p_1(H-X)=0\). Combining this with (1) and \(\varepsilon(X,Y)\leq|X|\), we admit \[2p_0(H-X)=2p_0(H-X)+p_1(H-X)\geq b|X|-\varepsilon(X,Y)+1\geq b|X|-|X|+1\geq1,\] namely, \[\label{e2} p_0(H-X)\geq\frac{1}{2}.\tag{2}\]
According to (2) and the integrity of \(p_0(H-X)\), we get \[p_0(H-X)\geq1,\] which implies that there exists \(x_0\in V(H)\setminus X\) with \(d_{H-X}(x_0)=0\). Combining this with \(\delta(G)\geq2+k\) and \(H=G-Q\), we have \[\begin{aligned} 2+k&\leq&\delta(G)\leq d_G(x_0)\leq d_{G-Q}(x_0)+|Q|\\ &=&d_H(x_0)+k\leq d_{H-X}(x_0)+|X|+k=|X|+k, \end{aligned}\] that is, \[\label{e3} |X|\geq2.\tag{3}\]
Note that \(Y_0\neq\emptyset\) by \(p_0(H-X)\geq1\), and so \(N_G(Y_0)\neq V(G)\). In terms of (1), (3), \(\varepsilon(X,Y)\leq2\), \(p_1(H-X)=|Y_1|=0\) and \(b\geq2+k\geq2\), we get \[\begin{aligned} bind(G)&\leq&\frac{|N_G(Y_0)|}{|Y_0|}\leq\frac{|Q|+|X|}{|Y_0|}=\frac{k+|X|}{p_0(H-X)}\\ &=&\frac{2k+2|X|}{2p_0(H-X)+p_1(H-X)}\\ &\leq&\frac{2k+2|X|}{b|X|-\varepsilon(X,Y)+1}\leq\frac{2k+2|X|}{b|X|-1}\\ &=&\frac{2}{b}\cdot\Big(1+\frac{bk+1}{b|X|-1}\Big)\leq\frac{2}{b}\cdot\Big(1+\frac{bk+1}{2b-1}\Big)\\ &=&\frac{4+2k}{2b-1}\leq\frac{2b+2k}{2b-1}<\frac{2b+2k}{2b-2}=\frac{b+k}{b-1}, \end{aligned}\] which contradicts \(bind(G)>\frac{b+k}{b-1}\).
Case 2.\(Y_1\neq\emptyset\) and \(Y_1=N_{H-X}(Y_1)\).
We easily see that \(|Y_1|=2t\geq2\), where \(t\) is a positive integer. For \(x_1\in Y_1\), we admit \(d_{H-X}(x_1)=1\). Then using \(H=G-Q\) and \(\delta(G)\geq2+k\), we derive \[\begin{aligned} 2+k&\leq&\delta(G)\leq d_G(x_1)\leq d_{G-Q}(x_1)+|Q|\\ &=&d_H(x_1)+k\leq d_{H-X}(x_1)+|X|+k\\ &=&1+|X|+k, \end{aligned}\] namely, \[|X|\geq1.\]
If \(|X|=1\), then \(p_0(H-X)=0\) (since \(\delta(G)\geq2+k\)) and \(\varepsilon(X,Y)\leq1\). It follows from (1) and the hypothesis of Theorem 1 that \[\begin{aligned} \frac{b+k}{b-1}&<&bind(G)\leq\frac{|N_G(Y_1\setminus\{x_1\})|}{|Y_1\setminus\{x_1\}|}\leq\frac{|Q|+|X|+|Y_1|-1}{|Y_1|-1}\\ &=&\frac{k+|Y_1|}{|Y_1|-1}=\frac{k+p_1(H-X)}{p_1(H-X)-1}=1+\frac{1+k}{p_1(H-X)-1}\\ &=&1+\frac{1+k}{2p_0(H-X)+p_1(H-X)-1}\\ &\leq&1+\frac{1+k}{b|X|-\varepsilon(X,Y)}\leq1+\frac{1+k}{b|X|-1}=1+\frac{1+k}{b-1}\\ &=&\frac{b+k}{b-1}, \end{aligned}\] which is a contradiction. Next, we consider \(|X|\geq2\).
In light of (1), \(|X|\geq2\), \(\varepsilon(X,Y)\leq2\) and \(b\geq2+k\), we deduce \[\begin{aligned} bind(G)&\leq&\frac{|N_G(Y_0\cup(Y_1\setminus\{x_1\}))|}{|Y_0\cup(Y_1\setminus\{x_1\})|}\leq\frac{|Q|+|X|+|Y_1|-1}{|Y_0|+|Y_1|-1}\\ &=&\frac{k+|X|+p_1(H-X)-1}{p_0(H-X)+p_1(H-X)-1}\\ &=&1+\frac{k+|X|-p_0(H-X)}{p_0(H-X)+p_1(H-X)-1}\\ &\leq&1+\frac{k+|X|-p_0(H-X)}{b|X|-\varepsilon(X,Y)-p_0(H-X)}\\ &\leq&1+\frac{k+|X|-p_0(H-X)}{b|X|-2-p_0(H-X)}\leq1+\frac{k+|X|}{b|X|-2}\\ &=&1+\frac{1}{b}\cdot\Big(1+\frac{2+bk}{b|X|-2}\Big)\leq1+\frac{1}{b}\cdot\Big(1+\frac{2+bk}{2b-2}\Big)\\ &=&\frac{2b+k}{2b-2}\leq\frac{2b+2k}{2b-2}=\frac{b+k}{b-1}, \end{aligned}\] which contradicts \(bind(G)>\frac{b+k}{b-1}\).
Case 3.\(Y_1\neq\emptyset\) and \(Y_1\neq N_{H-X}(Y_1)\).
In this case, there exists \(x_2\in N_{H-X}(Y_1)\setminus Y_1\) with \(d_{H-X}(x_2)\geq2\), and so there exists \(x_3\in Y_1\) such that \(x_3x_2\in E(H-X)\) and \(x_3x\notin E(H-X)\) for any \(x\in V(H)\setminus(X\cup\{x_2\})\). Thus, we deduce \(|N_G(Y_0\cup Y_1)|\leq|Q|+|X|+|Y_1|\). Combining this with (1), \(|X|\geq1\) (since \(Y_1\neq\emptyset\) and \(\delta(G)\geq2+k\)), \(\varepsilon(X,Y)\leq2\), \(b\geq2+k\) and the hypothesis of Theorem 1, we infer \[\begin{aligned} \frac{b+k}{b-1}&<&bind(G)\leq\frac{|N_G(Y_0\cup Y_1)|}{|Y_0\cup Y_1|}\leq\frac{|Q|+|X|+|Y_1|}{|Y_0|+|Y_1|}\\ &=&\frac{k+|X|+p_1(H-X)}{p_0(H-X)+p_1(H-X)}\\ &=&1+\frac{k+|X|-p_0(H-X)}{p_0(H-X)+p_1(H-X)}\\ &=&1+\frac{k+|X|-p_0(H-X)}{2p_0(H-X)+p_1(H-X)-p_0(H-X)}\\ &\leq&1+\frac{k+|X|-p_0(H-X)}{b|X|-\varepsilon(X,Y)+1-p_0(H-X)}\\ &\leq&1+\frac{k+|X|-p_0(H-X)}{b|X|-1-p_0(H-X)}\\ &\leq&1+\frac{k+|X|}{b|X|-1}=1+\frac{1}{b}\cdot\Big(1+\frac{1+bk}{b|X|-1}\Big)\\ &\leq&1+\frac{1}{b}\cdot\Big(1+\frac{1+bk}{b-1}\Big)=\frac{b+k}{b-1}, \end{aligned}\] which is a contradiction. This finishes the proof of Theorem 1. ◻
We show that the binding number condition \(bind(G)>\frac{b+k}{b-1}\) in Theorem 1 cannot be replaced by \(bind(G)\geq\frac{b+k}{b-1}\).
We construct a graph \(G=K_{1+k}\vee(\frac{b}{2}K_2)\), where \(\vee\) means “join”, and \(b\) and \(k\) are two integers such that \(b\geq2+k\) and \(b\) is even. We easily deduce that \(bind(G)=\frac{b+k}{b-1}\). Let \(Q=V(K_k)\subseteq V(K_{1+k})\) and \(H=G-Q=K_1\vee(\frac{b}{2}K_2)\). We select \(X=V(K_1)\) and \(Y=\{x:x\in V(H)\setminus X, d_{H-X}(x)\leq2\}\) in \(H\). It is obvious that \(\varepsilon(X,Y)=1\) by the definition of \(\varepsilon(X,Y)\). Hence, we admit \[2p_0(H-X)+p_1(H-X)=b=b|X|-\varepsilon(X,Y)+1>b|X|-\varepsilon(X,Y).\] In light of Theorem 3, \(H\) is not a fractional \([2,b]\)-covered graph, and so \(G\) is not a fractional \((2,b,k)\)-critical covered graph.