The Diameter, Wide Diameter And Fault Diameter Of Some Interconnection Networks

Let G0 and G1 be two graphs with the same vertices. The new graph G(G0, G1; M) is a graph with vertex set V(G0)∪V(G1) and edge set E(G0)∪E(G1)∪M, where M is an arbitrary perfect matching between the vertices of G0 and G1, i.e., a set of cross edges with one endpoint in G0 and the other endpoint in G1.Let G0,G1,...,Gr-1 be r graphs with the same vertices.The new graph H= G(G0,G1,…,Gr-1;M) is a graph with vertex set V(H)= V(G0)∪V(G1)∪…∪V(Gr-1) and edge set E(H)= M∪E(G1)∪…∪E(Gr-1), where M=∪(?)Mi,i+1(modr) is arbi-trary perfect matchings between the vertices of Gi and Gi+1(mod r).We define the graph S Pn for n≥3.S P3 is a cycle of length 6 which is isomorphic to the star graph S3 and pancake graph P3. For n≥3, S Pn consists of n disjoint S Pn-1's, say S Pn-11,S Pn-12,S Pn-1n. The vertex set of each S Pn-1i for 1≤i≤n is divided arbitrarily into n-1 disjoint vertex sets equally, say Si,1,Si,2,...,Si,n-1. For every S Pn-1i and S Pn-1J, i≠j, there exists a perfect matching between Si,x and Sj,y for some x and y.In this paper, we will give the upper bounds of diameter, wide diameter and fault diameter of G(G0,G1;M), G(G0,G1,…,Gr-1;M) and S Pn.