Changing the Diameter in a Diagonal Mesh Network

Communication speed in a parallel and distributed system is related to the diameter of its underlying graph. The diameter of a graph can be affected by the addition or deletion of edges. In this paper we study how the diameter variability problem arises from change of edges of an m × n diagonal mesh, where m and n are not both even integers. We show that the least number of edges whose deletion from anm×n diagonal mesh will increase the diameter is no more than 2, and that the least number of edges whose addition to an m × n diagonal mesh causes the diameter to decrease is no more than dm/2en