The optimal unicyclic graphs for pair-connected reliability
type: Item
instance of: scholarly article
title: The optimal unicyclic graphs for pair-connected reliability
zbMATH Open document ID: 0773.05093
DOI: 10.1016/0166-218X(90)90057-J
author: Kyle T. Siegrist
author: Ashok T. Amin
author: Peter Slater
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: In a graph in which each edge operates independently with probability \(p\), the pair-connected reliability is the expected number of vertex pairs connected by paths of operating edges. Trees that maximize pair- connected reliability are stars, for every probability \(p\). For unicyclic graphs on \(k\) vertices, the authors establish that there is no such optimum; indeed, for each cycle length \(c\), \(3\leq c\leq k\), there is a probability \(p_ c\) and a \(k\)-vertex unicyclic graph \(G_ c\) having a \(c\)-cycle for which \(G_ c\) is the optimal \(k\)-vertex unicyclic graph for edge probability \(p_ c\).
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 90B25
zbMATH DE Number: 166478
zbMATH Keywords: pair-connected reliability
zbMATH Keywords: stars
zbMATH Keywords: unicyclic graphs
zbMATH Keywords: cycle
MaRDI profile type: Publication
cites work: The expected number of pairs of connected nodes: Pair-connected reliability
cites work: Q3798673
cites work: On the nonexistence of uniformly optimal graphs for pair-connected reliability
cites work: On unreliability polynomials and graph connectivity in reliable network synthesis
cites work: Maximizing the Mean Number of Communicating Vertex Pairs in Series-Parallel Networks
cites work: Greedy Colourings of Steiner Triple Systems
cites work: Network Resilience
cites work: Uniformly-most reliable networks do not always exist
full work available at URL: 0166-218x(90)90057-j
OpenAlex ID: W2050155662
Recommended article: On the nonexistence of uniformly optimal graphs for pair-connected reliability
Recommended article: On uniformly optimally reliable graphs for pair‐connected reliability with vertex failures
Recommended article: Uniformly optimal digraphs for strongly connected reliability
Recommended article: Q5472509
Recommended article: Uniformly optimally reliable graphs
Recommended article: Uniformly optimally reliable graphs: A survey
Recommended article: The node cop‐win reliability of unicyclic and bicyclic graphs
Recommended article: Q5455895
Recommended article: Classes of uniformly most reliable graphs for all-terminal reliability
Recommended article: Q4711903
description: scientific article; zbMATH DE number 166478