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.
Dankelmann, P. (2019). On the edge-connectivity of C_4-free graphs. Communications in Combinatorics and Optimization, 4(2), 141-150. doi: 10.22049/cco.2019.26453.1113
MLA
Peter Dankelmann. "On the edge-connectivity of C_4-free graphs". Communications in Combinatorics and Optimization, 4, 2, 2019, 141-150. doi: 10.22049/cco.2019.26453.1113
HARVARD
Dankelmann, P. (2019). 'On the edge-connectivity of C_4-free graphs', Communications in Combinatorics and Optimization, 4(2), pp. 141-150. doi: 10.22049/cco.2019.26453.1113
VANCOUVER
Dankelmann, P. On the edge-connectivity of C_4-free graphs. Communications in Combinatorics and Optimization, 2019; 4(2): 141-150. doi: 10.22049/cco.2019.26453.1113