Summary: [For the entire collection see Zbl 0583.00003.]
A common measure of network reliability is probabilistic connectedness, the probability that every site in a network can communicate with every other site. Studies typically assume that network links fail independently with uniform probability p and that sites never fail. Though #P-complete for general graphs, probabilistic connectedness can be measured in time linear in n, the number of links in the network, for series-parallel networks. It is remarkable that the most reliable series- parallel networks are generalized fans, maximal series-parallel networks with exactly two sites of degree two.
For some applications, a network may not be considered operational unless it has edge connectivity (cohesion) of at least k; for example, high cohesion may be necessary to avoid routing problems and queuing delay. We generalize probabilistic connectedness to k-cohesive connectedness and show that for 2-cohesive connectedness, generalized fans are again the most reliable maximal series-parallel networks.