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+24, 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²) 12 (G) ^3/2 - 12 (G), and we construct an infinite family of graphs to show that the exponent 3/2 of (G) in this bound is best possible.