CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  PublicationsjournalsCMB
Publications        
Abstract view

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

  Published:2009-12-04
 Printed: Jun 2010
  • Sizhong Zhou
Features coming soon:
Citations   (via CrossRef) Tools: Search Google Scholar:
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 graph, $(g, f)$-factor, $(g, f, n)$-critical graph, binding number
MSC Classifications: 05C70 show english descriptions Factorization, matching, partitioning, covering and packing 05C70 - Factorization, matching, partitioning, covering and packing
 

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