On the edge-connectivity of C_4-free graphs

Document Type: Original paper

Author

University of Johannesburg

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

Main Subjects