HIERARCHIC GRAPHS BASED ON THE FIBONACCI NUMBERS

Abstract

   

Keywords

• -

References

1. Sagan, “The Twisted n-cube with application to multiprocessing”, IEEE Transactions on Computers, vol.40, pp.88-93, 1991.
2. • The number of edges in HFC(n) ⎡ isf⎢⎣ n and lower diameter”, IEEE Transactions on Computers, vol. 40, pp. 1312-1316, 1991. the number of edges in HEFCk(n) is
3. K. Efe, “A variation on the hypercube with A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, “A class of hypercube-like networks”, Tech. Rep. EE/01/93, Dept. of Electrical Eng., Indian Institute of Science, Bangalore, 1993. k( fn n).[E(k+) k().[E(k+) ef().[E(k+) −k3−3 nk3−3 ∑3ief( i= ⎦⎥ −3+
4. • HFC(n)s have node degrees between ⎥⎥ Cubic Networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 6, pp.427-435, n⎤1 ⎢⎢ ⎡ HEFCk(n) is between ⎢⎢ )and (k +k )1⎤ ⎥⎥ (k n-1. W.-J. Hsu, “Fibonacci Cubes – A New Interconnection Topology”, IEEE Transactions on Parallel and Distributed Systems, vol. 4, pp. 12, 1993.
5. • All HFC(n), HEFC1(n), …, HEFCk(n) can be decomposed to lower sized HFC(r), HEFC1(r), …, HEFCk(r), r
6. Beppu Convention(B-Con) Plaza, Beppu City, Japan. • Due to HFC(n), HEFC1(n), …, HEFCk(n) having recurrent structures, recursive-descent and recursive-doubling algorithms can be [7] A. Karci, “Recursive Construction of developed on HFC(n), HEFC1(n), …, Hierarchical Fibonacci Cubes and Hierarchical HEFCk(n) easily, if these graphs are used as interconnection networks. Extended Fibonacci Cubes”, IEEE: 2001
7. International Conference on Parallel and Distributed Systems (ICPADS-2001), June 26
8. • If path P in one of HFC(n), HEFC HEFCk(n) contains three or more diagonal 29, 2001, KyongJu city, Korea. links, then P is not a shortest path.

9. J. Duato, S. Yalamanchili, and L. Ni, “Interconnection networks – An engineering approach”, IEEE Computer Society Press, 1997. diagonal links. Appendix edges (a) f h (b)