A Sufficient Condition for Fractional $(2,b,k)$-Critical Covered Graphs

1. Introduction

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 _{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\{\frac{|N_G(X)|}{|X|}:\mathrm{\varnothing }\ne X\subseteq V(G),N_G(X)\ne V(G)\}.$$

Let $a,b$ and $k$ be three nonnegative integers with $a\le b$. Then a spanning subgraph $F$ of $G$ is called an $[a,b]$-factor of $G$ if $a\le d_F(x)\le 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\le \sum _{e\ni x}h(e)\le 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.

We immediately get the following corollary by setting $k=0$ in Theorem 1.

We promptly obtain the following corollary if $b=2$ in Corollary 1.

2. The Proof of Theorem 1

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)\le a\}$, we define $\epsilon (X,Y)$ as follows: $$\epsilon (X,Y)=\{\begin{array}{ll}2,& \text{if}X\text{is not independent,}\\ 1,& \text{if}X\text{is independent and there is an edgejoining}\\ & X\text{and}V(G)\setminus (X\cup Y),\text{or there is anedge}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}$$

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.

The proof of Theorem 1 depends heavily on the following theorem, which is equivalent to Theorem 2.

3. Sharpness 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)\ge \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\ge 2+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)\le 2\}$ in $H$. It is obvious that $\epsilon (X,Y)=1$ by the definition of $\epsilon (X,Y)$. Hence, we admit $$2p_0(H-X)+p_1(H-X)=b=b|X|-\epsilon (X,Y)+1>b|X|-\epsilon (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.