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.