A sufficient condition for the existence of a k -factor excluding a given r -factor
Sizhong Zhou, Lan Xu, Yang Xu · Applied Mathematics and Nonlinear Sciences · 2017
Abstract Let G be a graph, and let k, r be nonnegative integers with k ≥ 2. A k -factor of G is a spanning subgraph F of G such that d F ( x ) = k for each x ∈ V ( G ), where d F ( x ) denotes the degree of x in F . For S ⊆ V ( G ), N G ( S ) = ∪ x ∊ S N G ( x ). The binding number of G is defined by bind ( G ) = min { | N G ( S ) | | S | : ∅ ≠ S ⊂ V ( G ) , N G ( S ) ≠ V ( G ) } $\begin{array}{} (G) = {\rm{min }}\{ \frac{{|{N_G}(S)|}}{{|S|}}:\emptyset e S \subset V(G),{N_G}(S) e V(G)\} \end{array}$ . In this paper, we obtain a binding number and neighborhood condition for a graph to have a k -factor excluding a given r -factor. This result is an extension of the previous results.