Large survivable nets and the generalized prisms (Q1897364): Difference between revisions

Let the vertices of a graph \(G\) be labelled by the numbers \(1, \dots, n\) and let \(\alpha\) be a permutation of \(\{1, \dots, n\}\). The \(\alpha\)- generalized prism \(\alpha (G)\) consists of two copies \(G_x\), \(G_y\) of \(G\) and of edges \((x_i, y_{\alpha (i)})\) for \(1\leq i\leq n\). If \(f\) is a graphical measure (numerical invariant) of \(G\), then \(\overline {f} (G)\) denotes the maximum value of \(f(H)\) taken over all subgraphs \(H\) of \(G\). When \(f\) is a vulnerability measure of a network \(G\), then \(G\) is viewed as survivable, if \(\overline {f} (G)= f(G)\), because then there are no especially attractive targets for an enemy. In the paper this condition is discussed for \(\alpha\)-generalized prisms and for \(f\) being the connectivity, the edge-connectivity or the minimum degree of a vertex. The result is a method to produce large survivable networks by repeatedly taking generalized prisms. Related polynomial algorithms are discussed.