A Neighborhood Condition for Graphs to Have \((g, f)\)-Factors

Abstract

Let \(G\) be a graph of order \(n\). Let \(a\) and \(b\) be integers with \(1 \leq a < b\), and let \(k \geq 2\) be a positive integer not larger than the independence number of \(G\). Let \(g(x)\) and \(f(x)\) be two non-negative integer-valued functions defined on \(V(G)\) such that \(a \leq g(x) \frac{(a+b)(k(a+b)-2)}{a+1}\) and \(|N_G(x_1) \cup N_G(x_2) \cup \cdots \cup N_G(x_k)| \geq \frac{(b-1)n}{a+b}\) for any independent subset \(\{x_1, x_2, \ldots, x_k\}\) of \(V(G)\). Furthermore, we show that the result is best possible in some sense.