$5$-Factor-Critical Graphs on the Torus

Abstract

A graph of order $n$ is said to be $k$-factor-critical for non-negative integer $k\le 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.