Canadian mathematical bulletin | |
A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical | |
关键词: graph; $(g; f)$-factor; $(g; f; n)$-critical graph; binding number; | |
DOI : 10.4153/CMB-2010-034-8 | |
学科分类:数学(综合) | |
来源: University of Toronto Press * Journals Division | |
【 摘 要 】
Let $G$ be a graph of order $p$, let $a$,$b$, and $n$ be nonnegative integers with $1leq alt b$, and let $g$and $f$ be two integer-valued functions defined on $V(G)$ suchthat $aleq g(x)lt f(x)leq b$ for all $xin V(G)$. A $(g,f)$-factorof graph $G$ is a spanning subgraph $F$ of $G$ suchthat $g(x)leq d_F(x)leq f(x)$ for each $xin 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)eq V(G)$. In this paper, it is provedthat $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} quadext{and}quad pgeqfrac{(a+b-1)(a+b-2)}{a+1}+frac{bn}{a}.] Furthermore, it isshown that thisresult is best possible in some sense.
【 授权许可】
Unknown
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201912050576706ZK.pdf | 36KB | download |