The connectivity and nature diagnosability of expanded $k$-ary $n$-cubes

Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 2, pp. 71-89

Connectivity and Diagnosability play an important role in measuring the fault tolerance of interconnection networks. As a topology structure of interconnection networks, the expanded $k$-ary $n$-cube $X{Q}^k$${}_n$ has many good properties. In this paper, we prove that (1) the connectivity of $X{Q}^k$${}_n$ is $4n$; (2) the nature connectivity of $X{Q}^k$${}_n$ is $8n-4$; (3) the nature diagnosability of $X{Q}^k$${}_n$ under the PMC model and MM${}^{*}$ model is $8n-3$ for $n\ge 2$.

Classification : 05C25, 05C90
Keywords: Interconnection networks, Combinatorics, Connectivity, Diagnosability, Expandedk-aryn-cubes

N.R. Adiga, M.A. Blumrich, D. Chen, P. Coteus, A. Gara, M.E. Giampapa, P. Heidelberger, S. Singh, B.D. Steinmacher−Burow, T. Takken, M. Tsao and P. Vranas, Blue Gene/L torus interconnection network. IBM J. Res. Dev. 49 (2005) 265–276. | DOI

F. Barsi, F. Grandoni and P. Maestrini, A theory of diagnosability of digital systems. IEEE Trans. Comput. 25 (1976) 585–593. | MR | Zbl | DOI

J.A. Bondy and U.S.R. Murty, Graph Theory. Springer, New York (2007). | MR | Zbl

Bella Bose, Bob Broeg, Younggeun Kwon and Yaagoub Ashir, Lee distance and topological properties of k-ary $n$-cubes. IEEE Trans. Comput. 44 (1995) 1021–1030. | MR | Zbl | DOI

Nai-Wen Chang and Sun−Yuan Hsieh, Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst. 25 (2014) 3002–3011. | DOI

A.T. Dahbura and G.M. Masson, An $O\left(n^{2.5}\right)$ fault identification algorithm for diagnosable systems, IEEE Trans. Comput. 33 (1984) 486–492. | Zbl | DOI

Kh. Day and A.-E. Al-Ayyoub and F. diameter of $k$-ary $n$-cube networks. IEEE Trans. Parallel and Distrib. Syst. 8 (1997) 903–907. | DOI

J. Fan, Diagnosability of crossed cubes under the comparison diagnosis model. IEEE Trans. Parallel Distrib. Syst. 13 (2002) 1099–1104. | DOI

Y. Hao and Shiying Wang, The 1-good-neighbor diagnosibility of augmented $k$-ary $n$-cubes. Adv. Appl. Math. 5 (2016) 762–772. | DOI

Th.W. Hungerford, Algebra. Springer-Verlag, New York (1974). | Zbl | MR

R.E. Kessler and J.L. Schwarzmeier, Cray T3D: a new dimension for Cray research, in Proc. 38th IEEE Comput. Soc. Inter. Confer., Spring, San Francisco (1993) 176–182.

P.-Lien Lai, J.M. Tan, Ch.-P. Chang and Lih−Hsing Hsu, Conditional diagnosability measures for large multiprocessor systems. IEEE Trans. Comput. 54 (2005) 165–175. | DOI

Cheng−Kuan Lin, Jimmy J.M. Tan, Lih−Hsing Hsu, Eddie Cheng and László Lipták, Conditional diagnosability of Cayley graphs generated by transposition trees under the comparison diagnosis model. J. Interconnection Netw. 9 (2008) 83–97. | DOI

J. Maeng and M. Malek, A comparison connection assignment for self-diagnosis of multiprocessor systems, in Proc. 11th Inter. Symp. Fault-Tolerant Comput. (1981) 173–175.

M. Noakes and W.J. Dally, System design of the J-machine, in: Proceedings of the sixth MIT conference on Advanced research in VLSI. MIT Press, Cambridge (1990) 179–194. | MR

Shao−Lun Peng, Cheng−Kuan Lin, Ji.J.M. Tan and Lih−Hsing Hsu, The g-good-neighbor conditional diagnosability of hypercube under PMC model. Appl. Math. Comput. 218 (2012) 10406–10412. | MR | Zbl

C. Peterson, J. Sutton and P. Wiley, iWarp: a 100-MOPS VLIW microprocessor for multicomputers. IEEE Micro 11 (1991) 26–37. | DOI

F.P. Preparata, G. Metze and R.T. Chien, On the connection assignment problem of diagnosable systems. IEEE Trans. Comput. EC-16 (1967) 848–854. | Zbl | DOI

Mujiangshan Wang, Yubao Guo and Shiying Wang, The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM${}^{*}$ model. Int. J. Comput. Math. 94 (2017) 620–631. | MR | Zbl | DOI

Mujiangshan Wang, Yuqing Lin and Shiying Wang, The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model. Theoret. Comput. Sci. 628 (2016) 92–100. | MR | Zbl | DOI

Shiying Wang and Weiping Han, The $g$-good-neighbor conditional diagnosability of $n$-dimensional hypercubes under the MM* model. Inf. Process. Lett. 116 (2016) 574–577. | MR | Zbl | DOI

Shiying Wang, Zhenhua Wang and Mujiangshan Wang, The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks. Comput. J. 59 (2016) 1839–1856. | MR | DOI

Shiying Wang, Zhenhua Wang and Mujiangshan Wang, The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks. Discrete Appl. Math. 217 (2017) 691–706. | MR | Zbl | DOI

Shiying Wang and Yuxing Yang, The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM* model. Appl. Math. Comput. 305 (2017) 241–250. | MR | Zbl

Yonghong Xiang and Iain A. Stewart, Augmented $k$-ary $n$-cubes. Inf. Sci. 181 (2011) 239–256. | MR | Zbl | DOI

Jun Yuan, Aixia Liu, Xue Ma, Xiuli Liu, Xiao Qin and Jifu Zhang, The $g$-good-neighbor conditional diagnosability of $k$-ary $n$-cubes under the PMC model and MM${}^{*}$ model. IEEE Trans. Parallel Distrib. Syst. 26 (2015) 1165–1177. | DOI

Jun Yuan, Aixia Liu, Xiao Qin, Jifu Zhang and Jing Li, $g$-Good-neighbor conditional diagnosability measures for 3-ary $n$-cube networks. Theoret. Comput. Sci. 622 (2016) 144–162. | MR | Zbl | DOI

Shurong Zhang and Weihua Yang, The g-extra conditional diagnosability and sequential $t/k$-diagnosability of hypercubes. Inter. J. Comput. Math. 93 (2016) 482–497. | MR | Zbl | DOI

Nan Zhao and Shiying Wang, The 1-good-neighbor diagnosability of augmented 3-ary $n$-cubes. Adv. Appl. Math. 5 (2016) 754–761. | DOI