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

Canadian mathematical bulletin

关键词: 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