Wide Diameters of Cartesian Product Graphs and Digraphs

被引：0
作者：
Jun-Ming Xu
机构：
[1] Universtiy of Science and Technology of China,Deparment of Mathematics
来源：
Journal of Combinatorial Optimization | 2004年 / 8卷
关键词：
connectivity; diameter; wide diameter; cartesian product; networks; fault tolerance;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：171 / 181
页数：10
相关论文
共 37 条
[1]  
Bermond J.-C.(1986)Strategies for interconnection networks: Some methods from graph theory J. Parallel Distri. Comput. 3 433-449
[2]  
Delorme C.(1984)Generalized hypercube and hyperbus structures for a computer network IEEE Trans. Comput. 33 323-333
[3]  
Quisquater J.-J.(1999)Fault tolerance properties of pyramid networks IEEE Trans Comput. 46 88-93
[4]  
Bhuyan L.N.(1993)Line digraph iterations and connectivity analysis of de Bruijn and Kautz graphs IEEE Trans. Computers 42 612-616
[5]  
Agrawal D.P.(1996)Combinatorial properties of generalized hypercube graphs Information Processing Letters 57 41-45
[6]  
Cao F.(1994)Mengerian properties, Hamiltonicity and claw-free graphs Networks 24 660-678
[7]  
Du D.-Z.(1989)Hypercube supercomputers Proc. IEEE 77 1829-1841
[8]  
Hsu D.F.(1994)On container width and length in graphs, groups, and networks IEICE Trans, Fundam E77A 668-680
[9]  
Teng S.H.(1994)Note on the Discrete Math 132 291-296
[10]  
Du D.-Z.(1996)-diameter of Networks 27 257-266
1234