## Abstract

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 - 2 δ (G) - n (G) .For graphs that, in addition, contain no 3-cycle, we improve this bound even further.

Original language | English |
---|---|

Pages (from-to) | 2111-2117 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 155 |

Issue number | 16 |

DOIs | |

Publication status | Published - 1 Oct 2007 |

Externally published | Yes |

## Keywords

- C-free graph
- Connectivity
- Diamond-free graph
- Minimum degree

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics