On designing a network to defend against random attacks of radius two

✍ Scribed by A. S. Finbow; B. L. Hartnell

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 725 KB
• Volume: 19
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230190704

✦ Synopsis

This paper considers the following variation on the construction of a reliable communication network. Whenever a vertex is attacked, all vertices within distance 2 are also destroyed (or fail) indirectly. We are interested in designing a connected graph (undirected, all edges of length one) on p vertices such that when a random subset of the vertices are attacked the expected number of vertices that are destroyed (directly and indirectly) is minimized. It is assumed that any of the 2P subsets of vertices is equally likely to be attacked. The optimal structure is determined for all p and is shown to be one of five patterns depending on r where p = 5t + r.