Large survivable nets and the generalized prisms
type: Item
instance of: scholarly article
title: Large survivable nets and the generalized prisms
zbMATH Open document ID: 0827.05036
DOI: 10.1016/0166-218X(94)00131-V
author: Hong-Jian Lai
published in: Discrete Applied Mathematics
publication date: 1995-11-27T00:00:00Z
review text: 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.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 790499
zbMATH Keywords: survivable net
zbMATH Keywords: vulnerability
zbMATH Keywords: connectivity
zbMATH Keywords: edge-connectivity
zbMATH Keywords: minimum degree of a vertex
zbMATH Keywords: survivable networks
zbMATH Keywords: generalized prisms
zbMATH Keywords: polynomial algorithms
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q5598189
cites work: Q5545841
cites work: The size of strength‐maximal graphs
cites work: k-Degenerate Graphs
cites work: Minimale \(n\)-fach kantenzusammenhängende Graphen
cites work: k-Components, Clusters and Slicings in Graphs
cites work: Q4159404
cites work: Q3834076
cites work: Connectivity of generalized prisms over G
cites work: On cycle permutation graphs
cites work: Q5677514
description: scientific article; zbMATH DE number 790499