The Restricted Edge-connectivity And Restricted Arc-connectivity Of Strong Product Graphs

The multiprocessor interconnection networks are conveniently modeled by graphs or digraphs, in which the vertex corresponds to processor and the edge (arc) corresponds to communication link. One fundamental consideration in the design of such networks is the reliability, which can usually be measured by the edge-connectivity (arc-connectivity) of the graph (digraph). The larger the edge-connectivity (arc-connectivity) is, the more reliable the network is. Besides the edge-connectivity, the restricted edge-connectivity has been broadly concerned recently. The article is divided into three chapters, in which, the restricted edge-connectivity of strong product graphs and the restricted arc-connectivity of strong product digraphs are studied.In Chapter 1, we give some basic notations and terminologies on graphs.In Chapter 2, we introduce the concept of strong product graphs and give a upper bound and a lower bound of the restricted edge-connectivity of strong product graphs and some corollaries.(1) Let G1 and G1 be two connected graphs with connectivityλ1 andλ2, respectively. Then(2) Let G be a connected graph with connectivityλand |V(G)|>2. Thenλ'(K2(?) G)=4A.(3)Let G1 and G1 be two connected graphs with connectivityλ1 andλ2, respectively. Then(4)If G1 and G1 are two maximally edge-connected graphs andσ≥2,σ2≥2, then G1(?)G2 is super edge-connected.(5)Let D=Cm(?)Cn and m, n≥3. Thenλ'(D)=14.In Chapter 3, we study the restricted arc-connectivity of a class of strong product digraphs. The main results are as follows:(1) Let Di(i=1,2) be a nontrivial strongly connected digraph with order ni and arc-connectivityλi and let D=D1(?)D2. Then(2) Let D1 be a nontrivial strongly connected digraph such that|V(D1)|＞2 and letσandλbe the minimum degree and arc-connectivity, respectively. Ifσ+=σ-=σ, thenλ'(C2(?)D1)=4A.