|
|
Results 1 - 1 of 1 |
1. CMB 2009 (vol 53 pp. 378)
| A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical 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 integer-valued 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 non-empty 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+b-1)(p-1)}{(a+1)p-(a+b)-bn+2}
\quad\text{and}\quad p\geq
\frac{(a+b-1)(a+b-2)}{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 Category:05C70 |

