@article {
author = {Dankelmann, Peter},
title = {On the edge-connectivity of C_4-free graphs},
journal = {Communications in Combinatorics and Optimization},
volume = {4},
number = {2},
pages = {141-150},
year = {2019},
publisher = {Azarbaijan Shahid Madani University},
issn = {2538-2128},
eissn = {2538-2136},
doi = {10.22049/cco.2019.26453.1113},
abstract = {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.},
keywords = {edge-connectivity,maximally edge-connected,graph},
url = {http://comb-opt.azaruniv.ac.ir/article_13856.html},
eprint = {http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf}
}