Connectivity of Generalized Prisms Over G

Document Type

Article

Publication Date

2-28-1991

Department

Mathematics

School

Mathematics and Natural Sciences

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 α 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.

Publication Title

Discrete Applied Mathematics

Volume

30

Issue

40942

First Page

229

Last Page

233

Link to Full Text

Find in your library

Share

COinS