Conditions for k-factor-critical graphs
Xiaoyun Lv, Hongzhang Chen, Jianxi Li, Shou‐Jun Xu · RAIRO - Operations Research · 2025
For a nonnegative integer k, a graph G is said to be k-factor-critical if G − T has a perfect matching for any subset T ⊆ V (G) with |T | = k. In this paper, we first provide a condition in terms of the size of G to guarantee that G is k-factor-critical. For any graph G with minimum degree δ, we deduce a lower bound on the signless Laplacian spectral radius of G to ensure that G is k-factor-critical. Furthermore, we establish a condition based on Laplacian eigenvalues (resp. toughness) to determine whether a graph G is k-factor-critical. Additionally, we introduce a nullity condition for a t-connected graph to be k-factor-critical.