A t-container Ct(u,v)is a set of t internally disjoint paths between two distinct vertices u and v in a graph G,i.e.,Ct(u,v)={P_(1),P_(2),···,Pt}.Moreover,if V(P_(1))∪V(P_(2))∪···∪V(Pt...A t-container Ct(u,v)is a set of t internally disjoint paths between two distinct vertices u and v in a graph G,i.e.,Ct(u,v)={P_(1),P_(2),···,Pt}.Moreover,if V(P_(1))∪V(P_(2))∪···∪V(Pt)=V(G)then Ct(u,v)is called a spanning t-container,denoted by C_(t)^(sc)(u,v).The length of C_(t)^(sc)(u,v)={P_(1),P_(2),···,Pt}is l(C_(t)^(sc)(u,v))=max{l(P_(i))|1≤i≤t}.A graph G is spanning t-connected if there exists a spanning t-container between any two distinct vertices u and v in G.Assume that u and v are two distinct vertices in a spanning t-connected graph G.Let D_(t)^(sc)(u,v)be the collection of all C_(t)^(sc)(u,v)’s.Define the spanning t-wide distance between u and v in G,d_(t)^(sc)(u,v)=min{l(C_(t)^(sc)(u,v))|C_(t)^(sc)(u,v)∈D_(t)^(sc)(u,v)},and the spanning t-wide diameter of G,D_(t)^(sc)(G)=max{d_(t)^(sc)(u,v)|u,v∈V(G)}.In particular,the spanning wide diameter of G is D_(κ)^(sc)(G),whereκis the connectivity of G.In the paper we provide the upper and lower bounds of the spanning wide diameter of a graph,and show that the bounds are best possible.We also determine the exact values of wide diameters of some well known graphs including Harary graphs and generalized Petersen graphs et al..展开更多
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 the People's Republic of China“On disjoint path covers of graphs and related problems”(12261085)Natural Science Foundation of Xinjiang Uygur Autonomous Region of China“On spanning wide diameter and spanning cycle ability of interconnection networks”(2021D01C116)。
文摘A t-container Ct(u,v)is a set of t internally disjoint paths between two distinct vertices u and v in a graph G,i.e.,Ct(u,v)={P_(1),P_(2),···,Pt}.Moreover,if V(P_(1))∪V(P_(2))∪···∪V(Pt)=V(G)then Ct(u,v)is called a spanning t-container,denoted by C_(t)^(sc)(u,v).The length of C_(t)^(sc)(u,v)={P_(1),P_(2),···,Pt}is l(C_(t)^(sc)(u,v))=max{l(P_(i))|1≤i≤t}.A graph G is spanning t-connected if there exists a spanning t-container between any two distinct vertices u and v in G.Assume that u and v are two distinct vertices in a spanning t-connected graph G.Let D_(t)^(sc)(u,v)be the collection of all C_(t)^(sc)(u,v)’s.Define the spanning t-wide distance between u and v in G,d_(t)^(sc)(u,v)=min{l(C_(t)^(sc)(u,v))|C_(t)^(sc)(u,v)∈D_(t)^(sc)(u,v)},and the spanning t-wide diameter of G,D_(t)^(sc)(G)=max{d_(t)^(sc)(u,v)|u,v∈V(G)}.In particular,the spanning wide diameter of G is D_(κ)^(sc)(G),whereκis the connectivity of G.In the paper we provide the upper and lower bounds of the spanning wide diameter of a graph,and show that the bounds are best possible.We also determine the exact values of wide diameters of some well known graphs including Harary graphs and generalized Petersen graphs et al..
基金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.
