Lower‐bounds on the connectivities of a graph

Abstract

Abstract This article presents a study of the connectivities of a graph as a function of other graph parameters such as the number of vertices, the maximum degree, and the diameter. As a result, lower‐bounds on the connectivities of a graph as a function of these parameters are computed. These bounds could serve as sufficient conditions for a graph to be h ‐edge‐connected or k ‐connected. Consequently, the connectivity characteristics of many of the densest known graphs are determined.