The optimal unicyclic graphs for pair-connected reliability (Q1208486): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(90)90057-j / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2050155662 / rank | |||
Normal rank |
Latest revision as of 11:21, 30 July 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