TY - JOUR
ID - 13856
TI - On the edge-connectivity of C_4-free graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Dankelmann, Peter
AD - University of Johannesburg
Y1 - 2019
PY - 2019
VL - 4
IS - 2
SP - 141
EP - 150
KW - edge-connectivity
KW - maximally edge-connected
KW - graph
DO - 10.22049/cco.2019.26453.1113
N2 - 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.
UR - http://comb-opt.azaruniv.ac.ir/article_13856.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13856_bcb7a6a4d152a475da2d7bdfa37a581e.pdf
ER -