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-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.
Discrete Applied Mathematics
Piazza, B. L.,
(1991). Connectivity of Generalized Prisms Over G. Discrete Applied Mathematics, 30(40942), 229-233.
Available at: http://aquila.usm.edu/fac_pubs/6958