Abstract view
|
A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical
|
|
Published:2009-12-04
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 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
graph, $(g, f)$-factor, $(g, f, n)$-critical graph, binding number
|
