4.4 Application of the connectivity.

If we have a graph in our mind as representing a communication network, the connectivity becomes the smallest number of communication stations whose breakdown would destroy communication in the system.

Two statements are plausible:

-     The higher the connectivity and edge connectivity, the more reliable is the system.

-     The higher the connectivity and edge connectivity, the more expensive is the system.

So, the tree network is cheap, but it is not very reliable. This leads to consider the following generalisation of the spanning tree problem.

The Reliable Communication Network Problem: Let k be given positive integer and let G be a weighted graph. Determine a minimum-weight k-connected spanning subgraph of G.

-     If  then this problem reduces to the spanning tree problem.

-     If then the problem is unsolved and is known to be difficult.

-     If G is a complete graph in which edge is assigned unit weight, then the problem has a simple solution.

For a weighted complete graph on n vertices in which each edge is assigned unit weight, a minimum-weight k-connected spanning subgraph is a k-connected graph on n vertices with as few edges as possible. Let us denote by the least number of edges that a k-connected graph on n vertices can have. (It is clear that .)

From the Handshaking Lemma and the Whitney's Connectivity Theorem it follows immediately that

.

For given n and k Harary gave a construction for a graph which has exactly edges and he proved that  is k-connected. The structure of his construction depends on the parities of n and k, and it is as follows:

Case 1. k is even. Let Then is constructed as follows. It has vertices and two vertices i and j are joined if (where addition is taken modulo n.)

Case 2. k odd, n even. Let . Then constructed by first drawing and then adding edges joining vertex i to vertex .

Case 3. k odd, n odd. Let . Then is constructed by first drawing then adding edges joining vertex 0 to vertices and and vertex .

Figure 4.3. Some example for the Harary's construction