Abstract
The torus network is one of the most popular interconnection networks for massively parallel computing systems. The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. In this paper, we establish the strong matching preclusion number and classify all optimal solutions for the two-dimensional torus network with an odd number of vertices.
Acknowledgements
The authors would like to express their deepest gratitude to the anonymous referees for the constructive suggestions and comments that improve the quality of this paper. This work is supported by the National Natural Science Foundation of China (61370001) and the Doctoral Fund of Ministry of Education of China (20111401110005).