On the connectivity of diamond-free graphs

Let G be a graph of order n (G), minimum degree δ (G) and connectivity κ (G). Chartrand and Harary [Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61-63] gave the following lower bound on the connectivityκ (G) ≥ 2 δ (G) + 2 - n (G) .Topp and Volkmann [Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695-700] improved this bound to κ (G) ≥ 4 δ (G) - n (G), if G is bipartite and κ (G) < δ (G). In this paper, we show that this result remains valid for diamond-free graphs with δ (G) ≥ 3. A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge. Furthermore, we show that the above bounds can be improved significantly for graphs with δ (G) ≥ 3 and no 4-cycle, namely, if κ (G) < δ (G), thenκ (G) ≥ 2 δ (G)² + 2 - 2 δ (G) - n (G) .For graphs that, in addition, contain no 3-cycle, we improve this bound even further.