Wide diameter is an important parameter for measuring the reliability and efficiency of interconnection networks. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exi...Wide diameter is an important parameter for measuring the reliability and efficiency of interconnection networks. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k intemally disjoint paths of length at most d between any two distinct vertices in G. In this paper, we will discuss the wide diameter of two families of interconnection networks and present the bounds of r-1 wide diameter of G（G0,G1,...,Gr-1,L）, where L=Ui=1^r-1 Mi.j＋1, Mi.i.1 is an arbitrary perfect matching between V（Gi） and V（Gi＋1）, and G（G0,G1,F） , where F= {（uivi）[1 ≤ i ≤ n}U {（uivi＋1）｜1≤ i ≤ n}, ui ∈ V（G0）, vi ∈ V（G1）. And they are used in practical applications, especially in the distributed and parallel computer networks.展开更多
Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we...Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we show that the diameter and 3-wide diameter of generalized Petersen graph P（rn, a） are both O（m/2a）, where a ≥ 3.展开更多
基金Supported by the National Natural Science Foundation of China(11171097,61373019,201109574)
文摘Wide diameter is an important parameter for measuring the reliability and efficiency of interconnection networks. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k intemally disjoint paths of length at most d between any two distinct vertices in G. In this paper, we will discuss the wide diameter of two families of interconnection networks and present the bounds of r-1 wide diameter of G（G0,G1,...,Gr-1,L）, where L=Ui=1^r-1 Mi.j＋1, Mi.i.1 is an arbitrary perfect matching between V（Gi） and V（Gi＋1）, and G（G0,G1,F） , where F= {（uivi）[1 ≤ i ≤ n}U {（uivi＋1）｜1≤ i ≤ n}, ui ∈ V（G0）, vi ∈ V（G1）. And they are used in practical applications, especially in the distributed and parallel computer networks.
基金Supported by the National Natural Science Foundation of China (Grant No. 60973014)the Excellent Young Teachers Program of Shanghai Municipal Education Conmision (Grant No. B-8101-07-0027)Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 200801411073)
文摘Generalized Petersen graphs are commonly used interconnection networks, and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel processing computer networks. In this paper, we show that the diameter and 3-wide diameter of generalized Petersen graph P（rn, a） are both O（m/2a）, where a ≥ 3.
