2023/11/27 by Guo, Jing, Li, Qiuli, Lu, Fuliang +1 · 1 citation
#05C07 #05C70 #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.15821
A graph G of order n is said to be k-factor-critical for integers 1≤ k< n, if the removal of any k vertices results in a graph with a perfect matching. A k-factor-critical graph is minimal if for every edge, the deletion of it results in a graph that is not k-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal k-factor-critical graph has minimum degree k+1. In this paper, we confirm the conjecture for minimal k-factor-critical claw-free graphs. Moreover, we show that every minimal k-factor-critical claw-free graph G has at least (k-1)/(2k)|V(G)| vertices of degree k+1 in the case of (k+1)-connected, yielding further evidence for S. Norine and R. Thomas' conjecture on the minimum degree of minimal bricks when k=2.