The average connectivity of a graph Original Research Article

In this paper, we consider the concept of the average connectivity of a graph, defining it to be the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. Our main results are sharp bounds on the value of this parameter, and a construction of graphs whose average connectivity is the same as the connectivity. Along the way, we establish some new results on connectivity.