%0 Journal Article
%T On the edge-connectivity of C_4-free graphs
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Dankelmann, Peter
%D 2019
%\ 12/01/2019
%V 4
%N 2
%P 141-150
%! On the edge-connectivity of C_4-free graphs
%K edge-connectivity
%K maximally edge-connected
%K graph
%R 10.22049/cco.2019.26453.1113
%X 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.
%U http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf