Published in

Elsevier, Electronic Notes in Discrete Mathematics, (18), p. 53-58

DOI: 10.1016/j.endm.2004.06.009

Links

Tools

Export citation

Search in Google Scholar

Domination Invariant of a Diameter Constrained Network Reliability Model

Journal article published in 2004 by Héctor Cancela ORCID, Louis Petingi
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Red circle
Postprint: archiving forbidden
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Abstract Let G = (V;E) be a digraph with a distinguished set of terminal vertices K,V and a vertex s2 K. We dene,the s;K-diameter of G as the maximum distance between s and any of vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the Diameter-constrained s;K-terminal reliability of G, Rs;K(G;D), is dened as the probability that surviving arcs span a subgraph whose s;K-diameter does not exceed D. The Diameter-constrained network reliability is a special case of coherent system models, where the domination invariant has played an important role, both theoretically and for developing algorithms for reliability computation. In this work, we completely characterize the domination of diameter-constrained network models, giving a simple rule for computing its value: if the digraph either has an irrelevant edge, includes a dicycle or includes a dipath from s to a node in K longer than D, its domination is 0; otherwise, its domination is -1 to the powerjEj j Vj + 1. Key words: Graph theory, domination, diameter-constrained network reliability.