Abstract
The hypercube network Q n has been proved to be one of the most popular interconnection networks. The n-dimensional locally twisted cube LTQ n is an important variant of Q n . One of the critical performance factors of an interconnection network is the diameter which determines the maximum communication time between any pair of processors. In this paper, we investigate the diameter variability problems arising from the addition and deletion of edges in LTQ n . We obtain three results in this paper: (1) for any integer n≥2, we find the least number of edges (denoted by ch −(LTQ n )), whose deletion from LTQ n causes the diameter to increase, (2) for any integer n≥2, when ch −(LTQ n ) edges are deleted, the diameter will increase by 1 and (3) for any integer n≥4, the least number of edges whose addition to LTQ n will decrease the diameter is at most 2 n−1.
Acknowledgements
This work is supported by Natural Science Foundation of China (61170021), Specialized Research Fund for the Doctoral Program of Higher Education (20103201110018), Application Foundation Research of Suzhou of China (SYG201240), Natural Science Foundation of the Jiangsu Higher Education Institutions of China (12KJB520016), and sponsored by Qing Lan Project. And we would like to express our warmest gratitude to Prof. Jiwen Yang and Peide Qian for their instructive suggestions and valuable comments on the writing of this paper.