A graph of order \(n\) is said to be \(k\)-factor-critical for non-negative integer \(k \leq n\) if the removal of any \(k\) vertices results in a graph with a perfect matching. For a \(k\)-factor-critical graph of order \(n\), it is called \({trivial}\) if \(k = n\) and \({non-trivial}\) otherwise. Since toroidal graphs are at most non-trivial \(5\)-factor-critical, this paper aims to characterize all non-trivial \(5\)-factor-critical graphs on the torus.
Citation
Qiuli Li, Heping Zhang. \(5\)-Factor-Critical Graphs on the Torus[J], Ars Combinatoria, Volume 115. 357-366. .