Independence number and minimum degree for the existence of $(g,f,n)$-critical graphs. (English)
An. Ştiinţ. Univ. “Ovidius" Constanţa, Ser. Mat. 19, No. 1, 373-381 (2011).
Summary: Let $G$ be a graph, and let $g,f$ be two integer-valued functions defined on $V(G)$ with $0\leq g(x)\leq f(x)$ for each $x\in V(G)$. Then a spanning subgraph $F$ of $G$ is called a $(g,f)$-factor if $g(x)\leq d_F(x)\leq f(x)$ holds for each $x\in V(G)$. A graph $G$ is said to be $(g,f,n)$-critical if $G-N$ has a $(g,f)$-factor for each $N\subseteq V(G)$ with $\vert N\vert =n$. In this paper, we obtain an independence number and minimum degree condition for a graph $G$ to be a $(g,f,n)$-critical graph. Moreover, it is showed that the result in this paper is best possible in some sense.