A Note on Near-factor-critical Graphs

2014/04/22 by Kuo‐Ching Huang, Huang, Kuo-Ching, Ko‐Wei Lih +1
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1404.5416

openalex publication_date 2014/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A near-factor of a finite simple graph G is a matching that saturates all vertices except one. A graph G is said to be near-factor-critical if the deletion of any vertex from G results in a subgraph that has a near-factor. We prove that a connected graph G is near-factor-critical if and only if it has a perfect matching. We also characterize disconnected near-factor-critical graphs.

Citations

• The Factorization of Linear Graphs
• Polynomial reconstruction of the matching polynomial

Related

• Minimally k-factor-critical graphs for some large k
• Spectral condition for k-factor-criticality in t-connected graphs
• Matching and Factor-Critical Property in 3-Dominating-Critical Graphs
• Critical Equimatchable Graphs
• Spectral conditions for factor-criticality of graphs