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