Connectivity of generalized prisms over G.

The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used. For a graph G with vertices labeled 1,2,...,n and a permutation α in Sn, the generalized prisms over G,α(G) (also called a permutation graph), consists of two copies of G, say Gx and Gy, along with the edges (xi,yÅαÅ(iÅ)), for 1•i•n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, α(G), is determined for all α in the automorphism group of G.