2022/11/05 by Jing Guo, Heping Zhang, Guo, Jing +1 · 1 citation
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #F.2.2 #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory #\ 05C07
paper · pdf · doi:10.48550/arxiv.2211.02933
openalex publication_date 2022/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 G is called minimal if for any edge e∈ E(G), G-e is not k-factor-critical. In 1998, O. Favaron and M. Shi conjectured that every minimal k-factor-critical graph of order n has the minimum degree k+1 and confirmed it for k=1, n-2, n-4 and n-6. By using a novel approach, we have confirmed it for k = n - 8 in a previous paper. Continuing this method, we prove the conjecture to be true for k=n-10 in this paper.