The optimal unicyclic graphs for pair-connected reliability (Q1208486): Difference between revisions
From MaRDI portal
Revision as of 16:25, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The optimal unicyclic graphs for pair-connected reliability |
scientific article |
Statements
The optimal unicyclic graphs for pair-connected reliability (English)
0 references
16 May 1993
0 references
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\).
0 references
pair-connected reliability
0 references
stars
0 references
unicyclic graphs
0 references
cycle
0 references