On the connectivity of diamond-free graphs

Let GG be a graph of order n(G)n(G), minimum degree δ(G)δ(G) and connectivity κ(G)κ(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).κ(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)κ(G)⩾4δ(G)-n(G), if GG is bipartite and κ(G)<δ(G)κ(G)<δ(G). In this paper, we show that this result remains valid for diamond-free graphs with δ(G)⩾3δ(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δ(G)⩾3 and no 4-cycle, namely, if κ(G)<δ(G)κ(G)<δ(G), thenκ(G)⩾2δ(G)2+2-2δ(G)-n(G).κ(G)⩾2δ(G)2+2-2δ(G)-n(G).For graphs that, in addition, contain no 3-cycle, we improve this bound even further.