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

References

[1] C. Balbuena and A. Carmona, On the connectivity and superconnectivity of bipartite digraphs and graphs, Ars Combin. 61 (2001), 3–22.
[2] B. Bollobás, On graphs with equal edge connectivity and minimum degree, Discrete Math. 28 (1979), no. 3, 321–323.
[3] W.G. Brown, On graphs that do not contain a thomsen graph, Canad. Math. Bulletin 9 (1966), no. 3, 281–285.
[4] G. Chartrand, A graph-theoretic approach to a communications problem, SIAM J. Appl. Math. 14 (1966), no. 4, 778–781.
[5] P. Dankelmann, A. Hellwig, and L. Volkmann, On the connectivity of diamondfree graphs, Discrete Appl. Math. 155 (2007), no. 16, 2111–2117.
[6] P. Dankelmann, A. Hellwig, and L. Volkmann, Inverse degree and edge-connectivity, Discrete Math. 309 (2009), no. 9, 2943–2947.
[7] P. Dankelmann and L. Volkmann, New sufficient conditions for equality of minimum degree and edge-connectivity, Ars Combin. 40 (1995), 270–278.
[8] P. Dankelmann and L. Volkmann, Degree sequence conditions for maximally edge-connected graphs and digraphs, J. Graph Theory 26 (1997), no. 1, 27–34.
[9] P. Dankelmann and L. Volkmann, Degree sequence conditions for maximally edge-connected graphs depending on the clique number, Discrete Math. 211 (2000), no. 1-3, 217–223.
[10] P. Erdős and A. Rényi, On a problem in the theory of graphs (hungarian), Magyar Tud. Akad. Mat. Kutat´o. Int. K¨ozl. 7 (1962), 623–641.
[11] C. Godsil and G. Royle, Algebraic graph theory, Springer, New York, 2001.
[12] Y.O. Hamidoune, A property of a-fragments of a digraph, Discrete Math. 31 (1980), no. 1, 105–106.
[13] A. Hellwig and L. Volkmann, Maximally edge-connected digraphs, Australas. J. Combin. 27 (2003), 23–32.
[14] A. Hellwig and L. Volkmann, Maximally edge-connected and vertex-connected graphs and digraphs: A survey, Discrete Math. 308 (2008), no. 15, 3265–3296.
[15] L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math. 8 (1974), no. 4, 351–354.
[16] L. Volkmann, Bemerkungen zum p-fachen zusammenhang von graphen, An. Univ. Bucuresti Mat. 37 (1988), 75–79.
[17] L. Volkmann, Edge-connectivity in p-partite graphs, J. graph theory 13 (1989), no. 1, 1–6.
[18] L. Volkmann, Degree sequence conditions for maximally edge-connected oriented graphs, Applied Math. lett. 19 (2006), no. 11, 1255–1260.
[19] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150–168.
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 141-150

Files

Share

How to cite

Statistics