Abstract view
A New Sufficient Condition for a Graph To Be $(g,f,n)$Critical


Published:20091204
Printed: Jun 2010
Abstract
Let $G$ be a graph of order $p$, let $a$,
$b$, and $n$ be nonnegative integers with $1\leq a\lt b$, and let $g$
and $f$ be two integervalued functions defined on $V(G)$ such
that $a\leq g(x)\lt f(x)\leq b$ for all $x\in V(G)$. A $(g,f)$factor
of graph $G$ is a spanning subgraph $F$ of $G$ such
that $g(x)\leq d_F(x)\leq f(x)$ for each $x\in V(F)$. Then a graph
$G$ is called $(g,f,n)$critical if after deleting any $n$
vertices of $G$ the remaining graph of $G$ has a $(g,f)$factor.
The binding number $\operatorname{bind}(G)$ of $G$ is the minimum value of
${N_G(X)}/{X}$ taken over all nonempty subsets $X$ of
$V(G)$ such that $N_G(X)\neq V(G)$. In this paper, it is proved
that $G$ is a $(g,f,n)$critical graph if
\[
\operatorname{bind}(G)\gt \frac{(a+b1)(p1)}{(a+1)p(a+b)bn+2}
\quad\text{and}\quad p\geq
\frac{(a+b1)(a+b2)}{a+1}+\frac{bn}{a}.
\]
Furthermore, it is
shown that this
result is best possible in some sense.
Keywords: 
graph, $(g, f)$factor, $(g, f, n)$critical graph, binding number
graph, $(g, f)$factor, $(g, f, n)$critical graph, binding number
