Premium
Optimal consecutive‐2 systems of lines and cycles
Author(s) -
Du D. Z.,
Hwang F. K.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150405
Subject(s) - combinatorics , vertex (graph theory) , mathematics , graph , discrete mathematics
A consecutive‐2 system is a graph where each vertex can either work or fail and the system fails if and only if two vertices incident to the same edge both fail. The simplest probability structure attached to such systems is to assume that vertex i has probability p i of failing and the states of the vertices are stochastically independent. For a given graph G of n vertices and a given set P of n probabilities, an optimal consecutive‐2 system is the triple ( G,P,M ), where M is a mapping from P to the vertices of G such that the probability of the system failing is minimum. Consecutive‐2 systems have been widely studied when the graph is either a line or a cycle. In this paper we study optimal consecutive‐2 systems which consist of many lines or many cycles. Our results provide optimal mappings that depend only on the rankings of the individual failure probabilities and not on their actual values. Moreover, we show by examples that rankings alone are probably insufficient to solve cases more complex than those solved in this paper.