Connectivity versus Lin–Lu–Yau Curvature

Abstract We explore the interaction between connectivity and Lin–Lu–Yau curvature of graphs systematically. The intuition is that connected graphs with large Lin–Lu–Yau curvature also have large connectivity, and vice versa. We prove that the connectivity of a connected graph is lower bounded by the product of its minimum degree and its Lin–Lu–Yau curvature. On the other hand, if the connectivity of a graph G on n vertices is at least n-12, then G has positive Lin–Lu–Yau curvature. Moreover, the bound n-12 here is optimal. Furthermore, we prove that the edge-connectivity is equal to the minimum vertex degree for any connected graph with positive Lin–Lu–Yau curvature. As applications, we estimate or determine the connectivity and edge-connectivity of an amply regular graph with parameters (d, , ) such that 1.