Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T17:54:00.356Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimally Reliable Graphs for Both Vertex and Edge Failures

Published online by Cambridge University Press:  12 September 2008

D. H. Smith
D. H. Smith
Affiliation:
Department of Mathematics and Computing, University of Glamorgan, Pontypridd, Mid-Glamorgan, CF37 1DL, Wales, U.K.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider networks in which both the nodes and the links may fail. We represent the network by an undirected graph G. Vertices of the graph fail with probability p and edges of the graph fail with probability q, where all failures are assumed independent. We shall be concerned with minimising the probability P(G) that G is disconnected for graphs with given numbers of vertices and edges. We show how to construct these optimal graphs in many cases when p and q are ‘small’.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 1 , March 1993 , pp. 93 - 100
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bauer, D., Boesch, F., Suffel, C. and Tindell, R. (1981) Connectivity extremal problems and the design of reliable probabilistic networks. In: Chartrand, G., Alavi, Y., Goldsmith, D., Lesniak-Forster, L. and Lick, D. (Eds.) The Theory and Application of Graphs, Wiley 45–54.Google Scholar
[2]Bauer, D., Boesch, F., Suffel, C. and Tindell, R. (1985) Combinatorial optimization problems in the analysis and design of probabilistic networks. Networks 15 257–;271.CrossRefGoogle Scholar
[3]Bauer, D., Boesch, F. T., Suffel, C. and Van Slyke, R. (1987) On the validity of a reduction of reliable network design to a graph extremal problem. IEEE Trans. on Circuits and Systems CAS34 (12) 1579–1581.CrossRefGoogle Scholar
[4]Boesch, F. T. (1986) Synthesis of reliable networks – a survey. IEEE Trans. Reliability R35 (3) 240–246.CrossRefGoogle Scholar
[5]Boesch, F. T. (1986) On unreliability polynomials and graph connectivity in reliable network synthesis. J. Graph Theory 10 (3) 339–352.CrossRefGoogle Scholar
[6]Boesch, F. T. and Felzer, A. P. (1971) On the invulnerability of the regular complete k-partite graphs. SIAM J. Appl. Math. 20 176–182.CrossRefGoogle Scholar
[7]Boesch, F. T. and Frisch, I. T. (1968) On the smallest disconnecting set in a graph. IEEE Trans. Circuit Theory 15 (3) 286–288.CrossRefGoogle Scholar
[8]Boesch, F. T., Li, X. and Suffel, C. (1991) On the existence of uniformly optimally reliable networks. Networks 21 181–194.CrossRefGoogle Scholar
[9]Frank, H. (1969) Some new results in the design of survivable networks. Proc. 12th Ann. Midwest Circuit Theory Symp.,University of Texas, 13.1–13.8.Google Scholar
[10]Frank, H. (1969) Maximally reliable node weighted graphs. Proc. 3rd Ann. Conf. Information Sciences and Systems,Princeton University, 1–6.Google Scholar
[11]Hakimi, S. L. and Amin, A. T. (1973) On the design of reliable networks. Networks 3 241–260.CrossRefGoogle Scholar
[12]Smith, D. H. (1984) Graphs with the smallest number of minimum cut sets. Networks 14 47–61.CrossRefGoogle Scholar
[13]Smith, D. H. and Doty, L. L. (1990) On the construction of optimally reliable graphs. Networks 20 723–729.CrossRefGoogle Scholar