Conditions for k-factor-critical graphs

¹ School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu, P.R. China
² School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian, P.R. China

^* Corresponding author: shjxu@lzu.edu.cn

Received: 23 January 2024
Accepted: 2 July 2025

Abstract

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.