## Abstract

Let G be a connected graph of order n and minimum degree δ(G). The edge-connectivity λ(G) of G is the minimum number of edges whose removal renders G disconnected. It is well-known that λ(G) ≤ δ(G), and if λ(G) = δ(G), then G is said to be maximally edge-connected. A classical result by Chartrand gives the sufficient condition δ(G) ≥ ^{n−}_{2}^{1} for a graph to be maximally edge-connected. We give lower bounds on the edge-connectivity of graphs not containing 4-cycles that imply that for graphs not containing a 4-cycle Chartrand's condition can be relaxed to δ(G) ≥ ^{q n}_{2} +1, and if the graph also contains no 5-cycle, or if it has girth at least six, then this condition can be relaxed further, by a factor of approximately √2. We construct graphs to show that for an infinite number of values of n both sufficient conditions are best possible apart from a small additive constant.

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

Pages (from-to) | 141-150 |

Number of pages | 10 |

Journal | Communications in Combinatorics and Optimization |

Volume | 4 |

Issue number | 2 |

DOIs | |

Publication status | Published - Jun 2019 |

## Keywords

- Edge-connectivity
- Maximally edge-connected

## ASJC Scopus subject areas

- Control and Optimization
- Discrete Mathematics and Combinatorics

## Fingerprint

Dive into the research topics of 'On the edge-connectivity of C_{4}-free graphs'. Together they form a unique fingerprint.