To understand the motivation of what will follow, consider the three connected graphs in Figure 1.1. The first one can be disconnected by thendeletion of a vertex, x, which is a cut vertex of the graph.

              Figure 1.1. Three examples of graphs and their connectivity:

This is not the case with the second graph, which nevertheless can be disconnected by the deletion of two vertices, x and y. As to the third graph, it has no set of vertices by which deletion would disconnect it. In fact, this graph is complete and the only thing that can be done to it by deleting some vertices is to reduce it to a single vertex (remember that a graph has by definition at least one vertex). Looking at edges instead of vertices leads to similar observations concerning the smallest number of edges of the graph by which deletion would disconnect the graph. However,  if the graph has at least two vertices, it is always possible to disconnect it by deleting some edges (we do not have the equivalent of the preceding third case for vertices). If we see these graphs as models of communication networks, we understand the importance of these considerations concerning the vulnerability to breakdowns. We introduce a parameter of a graph which measures these properties. The connectivity κ(G) of a graph G is defined as the smallest number of vertices by which deletion in G yields a disconnected graph or a graph reduced to one vertex.

Let us formalize this definition. If there is in graph G a set of vertices

               A, which may be empty, such that G − A is disconnected, then:

otherwise:

(where n is the number of vertices of G).

The case  is characterized by the fact that in graph G any two vertices are joined by an edge. In other words G is a complete graph  (remember that G is simple). If that is the case, there is no set A of vertices such that G − A is disconnected. If it is not the case, there are in G two vertices not joined by an edge, x and y, and A = X {x, y} then has the property that G − A is disconnected. Since |A|≤ n − 2, we can deduce the

inequality 

Thus k(G) is bounded by:

The case  corresponds to G disconnected or n =1.

The other following inequality, to be verified, is based on the fact that if A is the set of neighbors of a vertex, then G−A is either disconnected or reduced to a single vertex. Considering a vertex of minimum degree δ_G, we deduce:

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(61-62)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength