Menu
A graph \(G\) is called a fractional ID-\((g,f)\)-factor-critical covered graph if for any independent set \(I\) of \(G\) and for every edge \(e \in E(G-I)\), \(G-I\) has a fractional \((g,f)\)-factor \(h\) such that \(h(e) = 1\). We give a sufficient condition using degree condition for a graph to be a fractional ID-\((g,f)\)-factor-critical covered graph. Our main result is an extension of Zhou, Bian, and Wu’s previous result [S. Zhou, Q. Bian, J. Wu, A result on fractional ID-\(k\)-factor-critical graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 87(2013) 229–236] and Yashima’s previous result [T. Yashima, A degree condition for graphs to be fractional ID-\([a,b]\)-factor-critical, Australasian Journal of Combinatorics 65(2016) 191–199].
The graphs discussed here are finite, undirected and simple. For a graph \(G\), its vertex set is denoted by \(V(G)\) and its edge set is denoted by \(E(G)\). For \(x\in V(G)\), we use \(N_G(x)\) to denote the set of vertices adjacent to \(x\) in \(G\), \(N_G[x]=N_G(x)\cup\{x\}\) and \(d_G(x)=|N_G(x)|\) is the degree of \(x\) in \(G\). Setting \(\delta(G)=\min\{d_G(x):x\in V(G)\}\). For \(S\subseteq V(G)\), \(G[S]\) denotes the subgraph of \(G\) induced by \(S\). We write \(G-S=G[V(G)\setminus S]\) and \(N_G(S)=\bigcup\limits_{x\in S}N_G(x)\). If \(N_G(S)\cap S=\emptyset\), then we call \(S\) independent. For \(X\subseteq E(G)\), \(G[X]\) denotes the subgraph of \(G\) induced by \(X\).
Let \(g\) and \(f\) be two integer-valued functions defined on \(V(G)\) satisfying \(0\leq g(x)\leq f(x)\) for any \(x\in V(G)\) and let \(h:E(G)\rightarrow[0,1]\) be a function with \(g(x)\leq\sum\limits_{e\ni x}h(e)\leq f(x)\) for any \(x\in V(G)\). Define \(F_h=\{e:h(e)>0,e\in E(G)\}\). Then we call \(G[F_h]\) a fractional \((g,f)\)-factor of \(G\) with indicator function \(h\). Naturally, a fractional \((g,f)\)-factor is a fractional \([a,b]\)-factor if \(g(x)=a\) and \(f(x)=b\) for all \(x\in V(G)\), and a fractional \([k,k]\)-factor is called a fractional \(k\)-factor. If \(h(e)\in\{0,1\}\) for any \(e\in E(G)\), then a fractional \((g,f)\)-factor, a fractional \([a,b]\)-factor and a fractional \(k\)-factor are called a \((g,f)\)-factor, an \([a,b]\)-factor and a \(k\)-factor, respectively.
A graph \(G\) is defined as a fractional ID-\((g,f)\)-factor-critical graph if \(G-I\) possesses a fractional \((g,f)\)-factor for any independent set \(I\) of \(G\). A graph \(G\) is defined as a fractional \((g,f)\)-covered graph if for any \(e\in E(G)\), \(G\) admits a fractional \((g,f)\)-factor with indicator function \(h\) satisfying \(h(e)=1\). Similarly, we may define a fractional ID-\([a,b]\)-factor-critical graph, a fractional ID-\(k\)-factor-critical graph, a fractional \([a,b]\)-covered graph and a fractional \(k\)-covered graph.
There are a rich literature on the existence of factors and fractional factors in graphs. More specifically, a great deal of results on the existence of factors in graphs with given properties can be discovered in [1-7], and a lot of results can be discovered in [8-12] related to the existence of fractional factors in graphs with prescribed properties. Zhou, Bian and Wu [13] demonstrated a degree condition for a graph being fractional ID-\(k\)-factor-critical. Yashima [14] posed a degree condition for a graph to be fractional ID-\([a,b]\)-factor-critical.
Theorem 1. ([13]) Let \(k\) be an integer with \(k\geq1\), and let \(G\) be a graph of order \(n\) with \(n\geq6k-2\) and \(\delta(G)\geq\frac{n}{3}+k\). If \(G\) satisfies \[\max\{d_G(x),d_G(y)\}\geq\frac{2n}{3}\] for each pair of nonadjacent vertices \(x,y\) of \(G\), then \(G\) is fractional ID-\(k\)-factor-critical.
Theorem 2. ([14]) Let \(b\geq a\geq1\) be integers, and let \(G\) be a graph of order \(n\) with \(n\geq\frac{(a+2b)(2a+b+1)}{b}\) and \(\delta(G)\geq\frac{bn}{a+2b}+a\). If \(G\) satisfies \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n}{a+2b}\] for each pair of nonadjacent vertices \(x,y\) of \(G\), then \(G\) is fractional ID-\([a,b]\)-factor-critical.
Combining the definition of a fractional ID-\((g,f)\)-factor-critical graph with that of a fractional \((g,f)\)-covered graph, we present the definition of a fractional ID-\((g,f)\)-factor-critical covered graph, that is, a graph \(G\) is called fractional ID-\((g,f)\)-factor-critical covered if \(G-I\) is fractional \((g,f)\)-covered for any independent set \(I\) of \(G\). A fractional ID-\((k,k)\)-factor-critical covered graph is simply called a fractional ID-\(k\)-factor-critical covered graph. In this article, we prove the following theorem for a graph being fractional ID-\((g,f)\)-factor-critical covered, which is a generalization of Theorems 1 and 2.
Theorem 3. Let \(a,b,r\) be integers with \(r\geq0\) and \(b-r\geq a\geq1\), let \(G\) be a graph of order \(n\) with \(n\geq\frac{(a+b)(2a+b+r)+2}{a+r}\) and \(\delta(G)\geq\frac{(a+r)n}{2a+b+r}+\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\), and let \(g,f:V(G)\rightarrow \mathbb{Z}\) be two functions with \(a\leq g(x)\leq f(x)-r\leq b-r\) for each \(x\in V(G)\). If \(G\) satisfies \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b+r}\] for each pair of nonadjacent vertices \(x,y\) of \(G\), then \(G\) is fractional ID-\((g,f)\)-factor-critical covered.
Using Theorem 3, the following two results hold.
Corollary 1. Let \(a,b\) be integers with \(b\geq a\geq1\), let \(G\) be a graph of order \(n\) with \(n\geq\frac{(a+b)(2a+b)+2}{a}\) and \(\delta(G)\geq\frac{an}{2a+b}+\frac{(b+1)^{2}-a(b-a+1)}{a}\), and let \(g,f:V(G)\rightarrow \mathbb{Z}\) be two functions with \(a\leq g(x)\leq f(x)\leq b\) for each \(x\in V(G)\). If \(G\) satisfies \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b}\] for each pair of nonadjacent vertices \(x,y\) of \(G\), then \(G\) is fractional ID-\((g,f)\)-factor-critical covered.
p
Corollary 2. Let \(k\) be an integer with \(k\geq1\), let \(G\) be a graph of order \(n\) with \(n\geq6k+\frac{2}{k}\) and \(\delta(G)\geq\frac{n}{3}+k+1+\frac{1}{k}\). If \(G\) satisfies \[\max\{d_G(x),d_G(y)\}\geq\frac{2kn+2}{3k}\] for each pair of nonadjacent vertices \(x,y\) of \(G\), then \(G\) is fractional ID-\(k\)-factor-critical covered.
The following result acquired by Li, Yan and Zhang [15] will be used to prove Theorem 3.
Theorem 4. ([15]) Let \(G\) be a graph, and let \(g,f:V(G)\rightarrow \mathbb{Z}\) be two functions with \(0\leq g(x)\leq f(x)\) for every \(x\in V(G)\). Then \(G\) is fractional \((g,f)\)-covered if and only if \[\delta_G(S,T)=f(S)-g(T)+\sum_{x\in T}d_{G-S}(x)\geq\varepsilon(S)\] for any \(S\subseteq V(G)\), where \(T=\{x:x\in V(G)\setminus S, d_{G-S}(x)\leq g(x)\}\) and \(\varepsilon(S)\) is defined by \[\varepsilon(S)=\left\{ \begin{array}{ll} 2,&\text{if} \ S \ \text{is not independent},\\ 1,&\text{if} \ S \ \text{is independent and there is an edge joining}\\ &S \ \text{and} \ V(G)\setminus(S\cup T), \ \text{or there is an edge} \ e=uv\\ &\text{joining} \ S \ \text{and} \ T \ \text{such that} \ d_{G-S}(v)=g(v) \ \text{for}v\in T,\\ 0,&\text{otherwise.}\\ \end{array} \right.\]
Proof of Theorem 3. Let \(I\) be an independent set of \(G\), and let \(H=G-I\). In order to prove Theorem 3, it suffices to show that \(H\) is fractional \((g,f)\)-covered. Assume that \(H\) is not fractional \((g,f)\)-covered. Then by Theorem 4, we have \[\label{e1} \delta_H(S,T)=f(S)-g(T)+\sum_{x\in T}d_{H-S}(x)\leq\varepsilon(S)-1\tag{1}\] for some \(S\subseteq V(H)\), where \(T=\{x: x\in V(H)\setminus S, d_{H-S}(x)\leq g(x)\}\).
Claim 1. \(|I|\leq\frac{(a+r)n-2}{2a+b+r}\).
Proof. Note that \(n\geq\frac{(a+b)(2a+b+r)+2}{a+r}\). Thus, the inequality holds for \(0\leq|I|\leq1\). Next, we assume that \(|I|\geq2\). It follows from the hypothesis of Theorem 3 and \(I\) being an independent set of \(G\) that \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b+r}\] for any two distinct vertices \(x,y\in I\). Thus, we acquire \[|I|+\frac{(a+b)n+2}{2a+b+r}\leq|I|+\max\{d_G(x),d_G(y)\}\leq n,\] namely, \[|I|\leq\frac{(a+r)n-2}{2a+b+r}.\] Claim 1 is demonstrated. ◻
Note that \(\varepsilon(S)\leq|S|\). If \(T=\emptyset\), then using (1), we gain \(\varepsilon(S)-1\geq\delta_H(S,T)=f(S)\geq(a+r)|S|\geq|S|\geq\varepsilon(S)\), a contradiction. Hence, \(T\neq\emptyset\). Let \[h_1=\min\{d_{H-S}(x):x\in T\},\] and select \(x_1\in T\) with \(d_{H-S}(x_1)=h_1\). If \(T\setminus N_T[x_1]\neq\emptyset\), then we write \[h_2=\min\{d_{H-S}(x):x\in T\setminus N_T[x_1]\},\] and select \(x_2\in T\setminus N_T[x_1]\) with \(d_{H-S}(x_2)=h_2\). Apparently, \(0\leq h_1\leq h_2\leq b-r\).
In what follows, the proof is divided into two cases.
Case 1. \(T=N_T[x_1]\).
Claim 2. \(|S|+d_{H-S}(x)>b-r+1\) for every \(x\in T\).
Proof. According to Claim 1, \(\delta(G)\geq\frac{(a+r)n}{2a+b+r}+\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\) and \(H=G-I\), we have \[\begin{aligned} |S|+d_{H-S}(x)&\geq&d_H(x)=d_{G-I}(x)\geq d_G(x)-|I|\geq\delta(G)-|I|\\ &\geq&\frac{(a+r)n}{2a+b+r}+\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\\ &&-\frac{(a+r)n-2}{2a+b+r}\\ &=&\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}+\frac{2}{2a+b+r}\\ &>&\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\\ &=&\frac{(b-a-2r+1)^{2}+(a+r)(b-r+1)}{a+r}\\ &\geq&b-r+1 \end{aligned}\] for every \(x\in T\). Claim 2 is verified. ◻
Claim 3. \(|T|\geq a+r+1\).
Proof. Assume \(|T|\leq a+r\). Then it follows from (1), \(\varepsilon(S)\leq2\), \(T\neq\emptyset\) and Claim 2 that \[\begin{aligned} 1&\geq&\varepsilon(S)-1\geq\delta_H(S,T)=f(S)-g(T)+\sum_{x\in T}d_{H-S}(x)\\ &\geq&(a+r)|S|-(b-r)|T|+\sum_{x\in T}d_{H-S}(x)\\ &\geq&|T||S|-(b-r)|T|+\sum_{x\in T}d_{H-S}(x)\\ &=&\sum_{x\in T}(|S|+d_{H-S}(x)-(b-r))\\ &>&\sum_{x\in T}(b-r+1-(b-r))\\ &=&|T|\geq1, \end{aligned}\] this is a confliction. The proof of Claim 3 is finished. ◻
Note that \(|T|=|N_T[x_1]|\leq d_{H-S}(x_1)+1=h_1+1\). Combining this with \(0\leq h_1\leq b-r\), we acquire \[\label{e2} |T|\leq h_1+1\leq b-r+1.\tag{2}\]
Using (2) and Claim 3, we have \[a+r+1\leq|T|\leq h_1+1\leq b-r+1,\] which implies \[\label{e3} h_1\geq a+r\tag{3}\] and \[\label{e4} b\geq a+2r.\tag{4}\]
By Claim 1, \(H=G-I\) and \(\delta(G)\geq\frac{(a+r)n}{2a+b+r}+\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\), we get \[\begin{aligned} |S|+h_1&=&|S|+d_{H-S}(x_1)\geq d_H(x_1)=d_{G-I}(x_1)\\ &\geq&d_G(x_1)-|I|\geq\delta(G)-|I|\\ &\geq&\frac{(a+r)n}{2a+b+r}+\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}\\ &&-\frac{(a+r)n-2}{2a+b+r}\\ &=&\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}+\frac{2}{2a+b+r}\\ &>&\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}, \end{aligned}\] namely, \[\label{e5} |S|>\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}-h_1.\tag{5}\]
Using (1), (2), (3), (4), (5) and \(\varepsilon(S)\leq2\), we obtain \[\begin{aligned} 1&\geq&\varepsilon(S)-1\geq\delta_H(S,T)=f(S)-g(T)+\sum_{x\in T}d_{H-S}(x)\\ &\geq&(a+r)|S|-(b-r)|T|+h_1|T|\\ &=&(a+r)|S|-(b-r-h_1)|T|\\ &>&(a+r)\Big(\frac{(b-r+1)^{2}-(a+r)(b-a-2r+1)}{a+r}-h_1\Big)\\ &&-(b-r-h_1)(b-r+1)\\ &=&(h_1-a-r)(b-a-2r+1)+b-r+1\\ &\geq&b-r+1\geq a+1\geq2, \end{aligned}\] which is a confliction.
Case 2. \(T\neq N_T[x_1]\).
Note that \(x_1\in T\) and \(x_2\in T\setminus N_T[x_1]\). We easily see that \(x_1x_2\notin E(G)\). By the hypothesis of Theorem 3, \(H=G-I\) and \(0\leq h_1\leq h_2\leq b-r\), we have \[\begin{aligned} \frac{(a+b)n+2}{2a+b+r}&\leq&\max\{d_G(x_1),d_G(x_2)\}\\ &\leq&\max\{d_{H-S}(x_1)+|S|+|I|,d_{H-S}(x_2)+|S|+|I|\}\\ &=&\max\{h_1+|S|+|I|,h_2+|S|+|I|\}\\ &=&h_2+|S|+|I|, \end{aligned}\] namely, \[\label{e6} |S|\geq\frac{(a+b)n+2}{2a+b+r}-h_2-|I|.\tag{6}\]
Note that \(|S|+|T|+|I|\leq n\), \(h_2-h_1\geq0\), \(b-r-h_2\geq0\) and \(|N_T[x_1]|\leq d_{H-S}(x_1)+1=h_1+1\). Combining these with (1) and \(\varepsilon(S)\leq2\), we derive \[\begin{aligned} &&(n-|S|-|T|-|I|)(b-r-h_2)\geq0\geq\delta_H(S,T)-\varepsilon(S)+1\\ &=&f(S)-g(T)+\sum_{x\in T}d_{H-S}(x)-\varepsilon(S)+1\\ &\geq&(a+r)|S|-(b-r)|T|+h_1|N_T[x_1]|+h_2(|T|-|N_T[x_1]|)-1\\ &=&(a+r)|S|-(b-r)|T|-(h_2-h_1)|N_T[x_1]|+h_2|T|-1\\ &=&(a+r)|S|-(h_2-h_1)|N_T[x_1]|-(b-r-h_2)|T|-1\\ &\geq&(a+r)|S|-(h_2-h_1)(h_1+1)-(b-r-h_2)|T|-1. \end{aligned}\] Therefore, \[(n-|S|-|I|)(b-r-h_2)\geq(a+r)|S|-(h_2-h_1)(h_1+1)-1.\] The inequality above implies \[\label{e7} (b-r-h_2)n-(a+b-h_2)|S|-(b-r-h_2)|I|+(h_2-h_1)(h_1+1)+1\geq0.\tag{7}\]
By (6), (7), Claim 1 and \(n\geq\frac{(a+b)(2a+b+r)+2}{a+r}\), we have \[\begin{aligned} 0&\leq&(b-r-h_2)n-(a+b-h_2)|S|-(b-r-h_2)|I|\\ &&+(h_2-h_1)(h_1+1)+1\\ &\leq&(b-r-h_2)n-(a+b-h_2)\Big(\frac{(a+b)n+2}{2a+b+r}-h_2-|I|\Big)\\ &&-(b-r-h_2)|I|+(h_2-h_1)(h_1+1)+1\\ &=&-\frac{((a+r)^{2}+(a+r)h_2)n}{2a+b+r}-\frac{2(a+b-h_2)}{2a+b+r}+(a+b-h_2)h_2\\ &&+(a+r)|I|+(h_2-h_1)(h_1+1)+1\\ &\leq&-\frac{((a+r)^{2}+(a+r)h_2)n}{2a+b+r}-\frac{2(a+b-h_2)}{2a+b+r}+(a+b-h_2)h_2\\ &&+\frac{(a+r)((a+r)n-2)}{2a+b+r}+(h_2-h_1)(h_1+1)+1\\ &=&-\frac{(a+r)h_2n}{2a+b+r}+(a+b-h_2)h_2+(h_2-h_1)(h_1+1)\\ &&+\frac{2h_2}{2a+b+r}-1.\\ \end{aligned}\] Hence, \[\label{e8} -\frac{(a+r)h_2n}{2a+b+r}+(a+b-h_2)h_2+(h_2-h_1)(h_1+1)+\frac{2h_2}{2a+b+r}-1\geq0.\tag{8}\]
Note that \(0\leq h_1\leq h_2\leq b-r\). First assume \(h_2=0\). Then \(h_1=0\), and thus it follows from (8) that \(-1\geq0\), a contradiction. We next discuss \(1\leq h_2\leq b-r\).
Let \[F(h_1,h_2)=-\frac{(a+r)h_2n}{2a+b+r}+(a+b-h_2)h_2+(h_2-h_1)(h_1+1)+\frac{2h_2}{2a+b+r}-1.\] Using \(0\leq h_1\leq h_2\leq b-r\), \(1\leq h_2\leq b-r\) and \(n\geq\frac{(a+b)(2a+b+r)+2}{a+r}\), we obtain \[\begin{aligned} \frac{\partial F(h_1,h_2)}{\partial h_2}&=&-\frac{(a+r)n}{2a+b+r}+a+b-h_2-h_2+h_1+1+\frac{2}{2a+b+r}\\ &\leq&-\frac{(a+r)n}{2a+b+r}+a+b-h_2+1+\frac{2}{2a+b+r}\\ &\leq&-\frac{(a+b)(2a+b+r)+2}{2a+b+r}+a+b+\frac{2}{2a+b+r}\\ &=&0, \end{aligned}\] which implies \[\label{e9} F(h_1,h_2)\leq F(h_1,h_1).\tag{9}\]
It follows from (8), (9), \(0\leq h_1\leq b-r\) and \(n\geq\frac{(a+b)(2a+b+r)+2}{a+r}\) that \[\begin{aligned} 0&\leq&F(h_1,h_2)\leq F(h_1,h_1)\\ &=&-\frac{(a+r)h_1n}{2a+b+r}+(a+b-h_1)h_1+\frac{2h_1}{2a+b+r}-1\\ &\leq&-\frac{((a+b)(2a+b+r)+2)h_1}{2a+b+r}+(a+b-h_1)h_1\\ &&+\frac{2h_1}{2a+b+r}-1\\ &=&-h_1^{2}-1\leq-1, \end{aligned}\] this is a confliction. We finish the proof of Theorem 3. ◻
Let \(G=(b-r)tK_1\vee(a+r)tK_1\vee((a+r)t+1)K_1\) be the complete 3-partite graph having three vertex sets of size \((b-r)t\), \((a+r)t\) and \((a+r)t+1\), respectively. So any two vertices contained in distinct vertex sets are adjacent and any two vertices contained in the same vertex set are not adjacent. Next, we show that the condition \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b+r}\] declared in Theorem 3 cannot be replaced by \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b+r}-1,\] where \(a,b,r,t\) are nonnegative integers such tat \(2\leq a=b-r\) and \(t\) is enough large. Setting \(|V(G)|=n\), we have \(n=(2a+b+r)t+1\). For for any two vertices \(x\) and \(y\) of \(((a+r)t+1)K_1\), we have \[\begin{aligned} \frac{(a+b)n+2}{2a+b+r}&>&\max\{d_G(x),d_G(y)\}=(b-r)t+(a+r)t=(a+b)t\\ &=&(a+b)\cdot\frac{n-1}{2a+b+r}=\frac{(a+b)n+2}{2a+b+r}-\frac{a+b+2}{2a+b+r}\\ &\geq&\frac{(a+b)n+2}{2a+b+r}-1 \end{aligned}\] Thus, we easily see that \[\max\{d_G(x),d_G(y)\}\geq\frac{(a+b)n+2}{2a+b+r}-1\] for any two nonadjacent vertices \(x,y\) of \(G\). Let \(I=V((a+r)tK_1)\). Then \(I\) is an independent set of \(G\). Setting \(H=G-I=(b-r)tK_1\vee((a+r)t+1)K_1\), \(S=V((b-r)tK_1)\) and \(T=V(((a+r)t+1)K_1)\). Define \(g(x)=b-r\) and \(f(x)=a+r\) for every \(x\in V(G)\). Note that \(\varepsilon(S)=0\). Thus, we acquire \[\begin{aligned} \delta_H(S,T)&=&f(S)-g(T)+\sum_{x\in T}d_{H-S}(x)\\ &=&(a+r)|S|-(b-r)|T|\\ &=&(a+r)(b-r)t-(b-r)((a+r)t+1)\\ &=&-(b-r)=-a<0=\varepsilon(S). \end{aligned}\] In light of Theorem 4, \(H\) is not fractional \((g,f)\)-covered, and so \(G\) is not fractional ID-\((g,f)\)-factor-critical covered.
My manuscript has no associated data.
The author declares no conflicts of interest to this work.
The author would like to thank the anonymous referees for their kind help and valuable suggestions which led to an improvement of this paper. This work was supported by the Natural Science Foundation of Shandong Province, China (ZR2023MA078) and supported by 333 Project of Jiangsu Province and Six Big Talent Peak of Jiangsu Province (Grant No. JY–022).