#### Title

Connectivity of Generalized Prisms Over G

#### Document Type

Article

#### Publication Date

2-28-1991

#### Department

Mathematics

#### Abstract

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-alpha in S(n), the generalized prisms over G, alpha-(G) (also called a permutation graph), consists of two copies of G, say G(x) and G(y), along with the edges (x(i), y-alpha-(i)), for 1 less-than-or-equal-to i less-than-or-equal-to 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, alpha-(G), is determined for all alpha in the automorphism group of G.

#### Publication Title

Discrete Applied Mathematics

#### Volume

30

#### Issue

40942

#### First Page

229

#### Last Page

233

#### Recommended Citation

Piazza, B. L.,
Ringeisen, R.
(1991). Connectivity of Generalized Prisms Over G. *Discrete Applied Mathematics, 30*(40942), 229-233.

Available at: http://aquila.usm.edu/fac_pubs/6958