The spined cube: a new hypercube variant with smaller diameter. (English) Zbl 1260.68027

Zhou, Wujun; Fan, Jianxi; Jia, Xiaohua; Zhang, Shukui

Inf. Process. Lett. 111, No. 12, 561-567 (2011).

Summary: Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known \(n\)-dimensional bijective connection graphs (BC graphs) is \(\lceil\frac{n+1}{2}\rceil\), given a fixed dimension \(n\). An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Möbius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the \(n\)-dimensional spined cube has the diameter \(\lceil n/3\rceil +3\) for any integer \(n\) with \(n\geq 14\). It is the first time in the literature that a hypercube variant with such a small diameter is presented.

MSC:

68M10	Network design and communication in computer systems
68M07	Mathematical problems of computer architecture
68R10	Graph theory (including graph drawing) in computer science

Keywords:

interconnection network; BC graph; spined cube; diameter

References:

[1]	Lee, S. C.; Hook, L. R., Logic and computer design in nanospace, IEEE Transactions on Computers, 57, 7, 965-977 (2008) · Zbl 1390.68038
[2]	Abraham, S.; Padmanabhan, K., The twisted cube topology for multiprocessors: a study in network asymmetry, Journal of Parallel and Distributed Computing, 13, 1, 104-110 (1991)
[3]	Efe, K., A variation on the hypercube with lower diameter, IEEE Transactions on Computers, 40, 11, 1312-1316 (1991)
[4]	Larson, S. M.; Cull, P., The Möbius cubes, IEEE Transactions on Computers, 44, 5, 647-659 (1995) · Zbl 1041.68522
[5]	Fan, J.; He, L., BC interconnection networks and their properties, Chinese Journal of Computers, 26, 1, 84-90 (2003)
[6]	Fan, J.; Jia, X., Edge-pancyclicity and path-embeddability of bijective connection graphs, Information Sciences, 178, 2, 340-351 (2008) · Zbl 1128.68075
[7]	Fan, J.; Lin, X., The \(t / k\)-diagnosability of the BC graphs, IEEE Transactions on Computers, 54, 2, 176-184 (2005)
[8]	Yang, X.; Cao, J.; Megson, G. M.; Luo, J., Minimum neighborhood in a generalized cube, Information Processing Letters, 97, 3, 88-93 (2006) · Zbl 1181.68045
[9]	Yang, X.; Megson, G. M.; Cao, J.; Luo, J., A lower bound on the size of \(k\)-neighborhood in generalized cubes, Applied Mathematics and Computation, 179, 1, 47-54 (2006) · Zbl 1110.68115
[10]	Yang, X.; Evans, D. J.; Megson, G. M., The locally twisted cubes, International Journal of Computer Mathematics, 82, 4, 401-413 (2005) · Zbl 1097.68522
[11]	Yang, X.; Megson, G. M.; Evans, D. J., Locally twisted cubes are 4-pancyclic, Applied Mathematics Letters, 17, 8, 919-925 (2004) · Zbl 1056.05074
[12]	Fan, J.; Jia, X.; Liu, X.; Zhang, S.; Yu, J., Efficient unicast in bijective connection networks with the restricted faulty node set, Information Sciences, 181, 11, 2303-2315 (2011) · Zbl 1216.68056
[13]	Cull, P.; Larson, S. M., A linear equation model for twisted cube networks, (Ni, L. M., ICPADS (1994), IEEE Computer Soc. Press), 709-715