Dankelmann, P. (2019). On the edge-connectivity of $C_4$-free graphs. Communications in Combinatorics and Optimization, (), -. doi: 10.22049/cco.2019.26453.1113

Peter Dankelmann. "On the edge-connectivity of $C_4$-free graphs". Communications in Combinatorics and Optimization, , , 2019, -. doi: 10.22049/cco.2019.26453.1113

Dankelmann, P. (2019). 'On the edge-connectivity of $C_4$-free graphs', Communications in Combinatorics and Optimization, (), pp. -. doi: 10.22049/cco.2019.26453.1113

Dankelmann, P. On the edge-connectivity of $C_4$-free graphs. Communications in Combinatorics and Optimization, 2019; (): -. doi: 10.22049/cco.2019.26453.1113

On the edge-connectivity of $C_4$-free graphs

Articles in Press, Accepted Manuscript , Available Online from 15 March 2019

Let $G$ be a connected graph of order $n$ and minimum degree $delta(G)$. The edge-connectivity $lambda(G)$ of $G$ is the minimum number of edges whose removal renders $G$ disconnected. It is well-known that $lambda(G) leq delta(G)$, and if $lambda(G)=delta(G)$, then $G$ is said to be maximally edge-connected. A classical result by Chartrand gives the sufficient condition $delta(G) geq frac{n-1}{2}$ 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 $delta(G) geq sqrt{frac{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 $sqrt{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.