Connectivity Connectivity is usually used to describe the reliability of the network. In a network, if there is a path connecting nodes i and j after removing (k
1) other nodes and their associated links, then i and j are said to be k-connected. Anetwork is said to be k-connected if any pair of nodes are k-connected. Therefore, a k-connected network can survive (k
1) node failures. Another notion of interest is arc connectivity.

This is defined as the minimum number of links that need to be removed in order to disconnect the network. In other words, a k arc-connected network can withstand at least (k
1) link failures.

(a) Determine the node and arc connectivity of star, tree, ring, and cellular network topologies.

(b) Determine the node and arc connectivity of the two ad hoc topologies, shown in Figure 8.26.