Wide Diameters of Cartesian Product Graphs and Digraphs
Tóm tắt
In graph theory and study of fault tolerance and transmission delay of networks, connectivity and diameter of a graph are two very important parameters and have been deeply studied by many authors. Wide diameter combining connectivity with diameter is a more important parameter to measure fault tolerance and efficiency of parallel processing computer networks and has received much attention in the recent years. Diameter with width k of a graph G is defined as the minimum integer d for which between any two distinct vertices in G there exist at least k internally disjoint paths of length at most d. In the present paper, the tight upper bounds of wide diameter of the Cartesian product graphs are obtained. Some known results can be deduced or improved from ours.
Tài liệu tham khảo
J.-C. Bermond, C. Delorme, and J.-J. Quisquater, “Strategies for interconnection networks: Some methods from graph theory. J. Parallel Distri. Comput., vol. 3, pp. 433–449, 1986.
L.N. Bhuyan and D.P. Agrawal, “Generalized hypercube and hyperbus structures for a computer network,” IEEE Trans. Comput., vol. 33, pp. 323–333, 1984.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan Press: London, 1976.
F. Cao, D.-Z. Du, D.F. Hsu, and S.H. Teng, “Fault tolerance properties of pyramid networks,” IEEE Trans Comput., vol. 46,no. 1, pp. 88–93, 1999.
D.-Z. Du, Y.-D. Lyuu, and D.F. Hsu, “Line digraph iterations and connectivity analysis of de Bruijn and Kautz graphs,” IEEE Trans. Computers, vol. 42,no. 5, pp. 612–616, 1993.
D.R. Duh, G.H. Chen, and D.F. Hsu, “Combinatorial properties of generalized hypercube graphs,” Information Processing Letters, vol. 57, pp. 41–45, 1996.
E. Flandrin and H. Li, “Mengerian properties, Hamiltonicity and claw-free graphs,” Networks, vol. 24, pp. 660–678, 1994.
J.P. Hayes and T.N. Mudge, “Hypercube supercomputers,” Proc. IEEE, vol. 77,no. 12, pp. 1829–1841, 1989.
D.H. Hsu, “On container width and length in graphs, groups, and networks,” IEICE Trans, Fundam, vol. E 77A, pp. 668–680, 1994.
D.H. Hsu and Y.D. Lyuu, “A graph-theoretical study of transmission delay and fault tolerance,” in Proc. of 4th ISMM International Conference on Parallel and Distributed Computing and Systems, 1991, pp. 20–24.
D.F. Hsu and T. Luczak, “Note on the k-diameter of k-regular k-connected graphs,” Discrete Math, vol. 132, pp. 291–296, 1994.
Y. Ishigami, “The wide-diameter of the n-dimensional torodal mesh,” Networks, vol. 27, pp. 257–266, 1996.
J.S. Jwo and T.C. Tuan, “On container length and connectivity in unidirectional hypercubes,” Networks, vol. 32, pp. 307–317, 1999.
M.S. Kirshnamoorthy and B. Krinamurthy, “Fault diameter of interconnection networks,” Comput. Math. Applic., vol. 13,nos. 5/6, pp. 577–582, 1987.
Q. Li, D. Sotteau, and J.-M. Xu, “2-diameter of de Bruijn graphs,” Networks, vol. 28,no. 1, pp. 7–14, 1996.
S.C. Liaw and G.J. Chang, “Wide diameters of Butterfly networks,” Taiwanese Journal of Mathematics, vol. 3,no. 1, pp. 83–88, 1999a.
S.C. Liaw and G.J. Chang, “Generalized diameters and Rabin numbers of networks,” J. Combinatorial Optimization, vol. 2, pp. 371–384, 1999b.
Y. Saad and M.H. Schultz, “Topogical properties of hypercubes,” IEEE Trans. Computers, vol. 37,no. 7, pp. 867–872, 1988.
J.-M. Xu, “Connectivity of Cartesian product digraphs and fault-tolerant routing of generalized hypercube,” Appl. Math.-JCU, vol. 13B,no. 2, pp. 179–187, 1998.
J.-M. Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers: Dordrecht/Boston/London, 2001.