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)

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) [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
How to Cite This Entry:
Graph, connectivity of a. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Graph,_connectivity_of_a&oldid=47122
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article