Strong matching preclusion for two-dimensional torus networks

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.

Keywords:

• interconnection networks
• torus
• cartesian product graphs
• strong matching preclusion
• fault tolerance

2010 AMS Subject Classifications:

• 68R10
• 94C15

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).