Binding Numbers for All Fractional $(a,b,k)$-Critical Graphs


Sizhong Zhou, Qiuxiang Bian, Zhiren Sun




Let $G$ be a graph of order $n$, and let $a$, $b$ and $k$ nonnegative integers with $2\leq a\leq b$. A graph $G$ is called all fractional $(a,b,k)$-critical if after deleting any $k$ vertices of $G$ the remaining graph of $G$ has all fractional $[a,b]$-factors. In this paper, it is proved that $G$ is all fractional $(a,b,k)$-critical if $n\geq\frac{(a+b-1)(a+b-3)+a}a+\frac{ak}{a-a}\text{ and }\operatoraname{bind}(G)>\frac{(a+b-1)(n-1)}{an-ak-(a+b)+2}$. Furthermore, it is shown that this result is best possible in some sense.