On the Edge-Connectivity of the Square of a Graph

Let G be a connected graph. The edge-connectivity of G, denoted by λ(G), is the minimum number of edges whose removal renders G disconnected. Let δ(G) be the minimum degree of G. It is well-known that λ(G) ≤ δ(G), and graphs for which equality holds are said to be maximally edge-connected. The square G² of G is the graph with the same vertex set as G, in which two vertices are adjacent if their distance is not more that $2$. In this paper we present results on the edge-connectivity of the square of a graph. We show that if the minimum degree of a connected graph G of order n is at least n+2/4, then G² is maximally edge-connected, and this result is best possible. We also give lower bounds on λ(G²) for the case that G² is not maximally edge-connected: We prove that λ(G²) ≥ κ(G)² + κ(G), where κ(G) denotes the connectivity of G, i.e., the minimum number of vertices whose removal renders G disconnected, and this bound is sharp. We further prove that λ(G²) ≥ 1/2λ(G)3/2 - 1/2 λ(G), and we construct an infinite family of graphs to show that the exponent $3/2$ of λ(G) in this bound is best possible.