On neighbor component order edge connectivity.

摘要

If a spy network is modeled as an undirected graph in which the nodes represent the spies and the edges are the communication links between spies, then consider the scenario where the interception of a link gives up both endnode spies. In graph-theoretic terms, edges fail and nodes do not, but when they do, the endnodes are subverted, i.e., removed, from the graph. Given k > 0, we say that upon the failure of some edges, the surviving subgraph is an operating state if it has at least one component of order ≥ k, and is a failure state otherwise. The neighbor component order edge connectivity, lambda( k)nc, is the minimum number of edge failures required to produce a failure state. We present some fundamental properties of this vulnerability parameter and determine its value for several well-known graphs. We also compare it with previously established vulnerability parameters. The complexity of calculating the neighbor component order edge connectivity of an arbitrary graph is equivalent to calculating an edge covering of the nodes for k = 1, and thus, is polynomial. However, the complexity becomes NP-hard for k = 2 as it is equivalent to calculating the edge domination number of a graph. Hence, we provide several polynomial time algorithms, including weighted trees and weighted cycles, as well as arbitrary trees and arbitrary unicycles. Finally, we study the unreliability of graphs, where edges can fail independently, with equal probability rho for 0 < rho < 1. A graph G is said to be uniformly most reliable if it has the smallest unreliability over all graphs in its class for all values of rho, and uniformly least reliable if it has the largest unreliability over all graphs in its class for all values of rho. We present results for the existence of uniformly most reliable and uniformly least reliable graphs for trees and unicycles.