Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals → CMB
Abstract view

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

Published:2009-12-04
Printed: Jun 2010
• Sizhong Zhou
 Format: HTML LaTeX MathJax

## 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
 MSC Classifications: 05C70 - Factorization, matching, partitioning, covering and packing

© Canadian Mathematical Society, 2014 : https://cms.math.ca/