Survivable Nets and the Generalized Permutation Graphs

Let f(G) denote a graphical function and define f¿(G) to be the maximum value of f(H) taken over all subgraph H of G. When f is a vulnerability measure of a network G, G can be viewed as survivable if f¿(G) = f(G) as defined in [1] and [2]. For the given graphs G, L, with a given orientation D = D(L), and for any map f: E(L) ¿ S_n, the permutation group on n elements, we define the graph GL,f which extend the notation of generalized prisms[3]. The purpose of this paper is to study the conditions when f(G^L,f) = f¿(G^L,f ) where f is the edge-connectivity and the minimum degree of a graph. Our results extend those in [4].