Graph, connectivity of a

One of the topological characteristics of a graph. A graph is said to be connected if for any two of its vertices $ u $ and $ v $ there exists a chain connecting these vertices. The vertex connectivity number of a graph $ G $( denoted by $ \kappa ( G) $) is the smallest number of vertices the removal of which results in a disconnected graph or in a graph consisting of one isolated vertex. The edge connectivity number (denoted by $ \lambda ( G) $) is the smallest number of edges of $ G $ the removal of which results in a disconnected graph. A graph $ G $ is said to be $ k $- connected if $ \kappa ( G) \geq k $, and $ k $- edge-connected if $ \lambda ( G) \geq k $. A maximal $ k $- connected subgraph of a graph $ G $ is said to be a $ k $- connected component of it; a $ 1 $- connected component is called a connected component. In studying communication networks and logical networks, the connectivity numbers of the corresponding graphs can be interpreted as a degree of reliability of these networks.

The theory of graphs studies methods for determining the connectivity of graphs, conditions under which a graph is $ k $- connected or $ k $- edge-connected, the relations between the different types of connectivity, the dependence of the connectivity numbers on other graph parameters, etc. Thus, if $ \delta ( G) $ is the minimal degree of the vertices of a graph $ G $, the following inequalities are valid: $ \kappa ( G) \leq \lambda ( G) \leq \delta ( G) $.

For any integers $ a, b, c $( $ 0 < a \leq b \leq c $) there exists a graph $ G $ for which $ \kappa ( G) = a $, $ \lambda ( G) = b $, $ \delta ( G) = c $. If $ G $ has $ n $ vertices and $ \delta ( G) \geq [ n/2] $, then $ \lambda ( G) = \delta ( G) $. One says that a set $ S $ of vertices, edges, or vertices and edges separates two vertices $ u $ and $ v $ if $ u $ and $ v $ belong to different connected components of the graph $ G- S $ obtained from $ G $ by the removal of the elements of $ S $. The following statements are valid.

The smallest number of vertices separating two non-adjacent vertices $ u $ and $ v $ is equal to the largest number of simple chains without common vertices connecting $ u $ and $ v $. A graph $ G $ is $ k $- connected if and only if any pair of its vertices is connected by at least $ k $ chains which do not intersect at the vertices. Similar theorems are also valid for edge connectivity. A graph is $ k $- edge-connected if and only if any pair of its vertices is connected by at least $ k $ chains which do not intersect at the edges. A set of edges whose removal results in the formation of a disconnected graph is known as a cut. In each graph the largest number of cuts which do not intersect at the edges and which separate two vertices $ u $ and $ v $ is equal to the smallest number of edges of a simple chain connecting $ u $ and $ v $, i.e. to the distance $ d ( u , v) $ between $ u $ and $ v $.

References

[1]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2]	L.R. Ford, D.R. Fulkerson, "Flows in networks" , Princeton Univ. Press (1962)

Comments

The assertions in the last section can be derived from the maximum-flow-minimum-cut theorem of L. Ford and D. Fulkerson (see [2]). The first two are different versions of the vertex form of Menger's theorem (see [1]).

The maximum-flow-minimum-cut theorem, or the Ford–Fulkerson theorem, deals with a directed graph $ G $ for which for each arc $ e $ a capacity $ 0 \leq c _ {e} < \infty $ is specified. In addition, two special vertices, labeled $ Q, S $, are specified, called source and sink respectively, and there are no arcs leaving $ S $ or entering $ Q $. A flow on the graph is given by specifying for every arc (i.e. directed edge) a number $ 0 \leq f _ {e} \leq c _ {e} $ such that for every vertex $ P \neq Q, S $,

$$ \tag{* } \sum _ {a ( e) = P } f _ {e} = \ \sum _ {b ( e) = P } f _ {e} $$

where for an arc $ e $, $ a ( e) $ denotes its source vertex and $ b ( e) $ its target vertex. The maximum flow problem asks for a flow such that

$$ \sum _ {a ( e) = Q } f _ {e} $$

is maximized. In this setting a cut is a set of arcs whose removal results in a disconnected graph with $ Q $ in one component and $ S $ in another. The capacity of a cut is the sum of the capacities $ c _ {e} $ of the elements of the cut. The maximum-flow-minimum-cut theorem now says that the maximum flow attainable is equal to the minimal attainable capacity of a cut. The maximum flow problem can be formulated as a linear programming problem, and then the maximum-flow-minimum-cut theorem is an instance of the duality theorem of linear programming.

Recall that a chain in a non-oriented graph from $ v _ {0} $ to $ v _ {n} $ is a sequence $ v _ {0} e _ {0} v _ {1} \dots e _ {n - 1 } v _ {n} $ of alternating vertices and edges such that $ e _ {i} $ is an edge between $ v _ {i} $ and $ v _ {i + 1 } $ and such that all $ e _ {j} $ and all $ v _ {k} $, except possibly $ v _ {0} $ and $ v _ {n} $, are distinct. A $ vw $- disconnecting set or cut, where $ v, w $ are two vertices, is a set of edges whose removal results in a disconnected graph with $ v $ in one component and $ w $ in another. The edge form of Menger's theorem now says that for a connected graph the maximum number of edge-disjoint chains from $ v $ to $ w $ is equal to the minimum number of edges in a $ vw $- disconnecting set. The theorem was in fact first proved by Ford and Fulkerson (1955). A $ vw $- separating set is a set of vertices $ S $( not including $ v $ or $ w $) such that any chain from $ v $ to $ w $ passes through $ S $. The vertex form of Menger's theorem (Menger, 1928) now says that the maximum number of vertex-disjoint chains connecting distinct non-adjacent vertices $ v $ and $ w $ is equal to the minimal number of vertices in a $ vw $- separating set. Menger's theorem is closely related to the P. Hall marriage theorem; cf. Combinatorial analysis for that theorem.

References

[a1]	W.T. Tutte, "Connectivity in graphs" , Oxford Univ. Press (1966) 0146.45603 Zbl 0146.45603
[a2]	R.J. Wilson, "Introduction to graph theory" , Longman (1985)
[a3]	H.-J. Walther, "Ten applications of graph theory" , Reidel (1984) pp. Sect. 6.1