66
Views
5
CrossRef citations to date
0
Altmetric
Section A

Strong matching preclusion for two-dimensional torus networks

&
Pages 473-485 | Received 22 Oct 2013, Accepted 01 Apr 2014, Published online: 08 May 2014
 

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.

2010 AMS Subject Classifications:

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

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.