Bounds on the connectivity of iterated line graphs

Abstract

For simple connected graphs that are neither paths nor cycles, we define l(G)=max{m : G has a divalent path of length m that is not both of length 2 and in a K₃}, where a divalent path is a path whose internal vertices have degree two in G. Let G be a graph and Lⁿ(G) be its n-th iterated line graph of G. We use κ_e′(G) and κ(G) for the essential edge connectivity and vertex connectivity of G, respectively. Let G be a simple connected graph that is not a path, a cycle or K_1, 3, with l(G)=l ≥ 1. We prove that (i) for integers s ≥ 1, κ′_e(L^l + s(G)) ≥ 2^s + 2; (ii) for integers s ≥ 2, κ(L^l + s(G)) ≥ 2^s − 1 + 2. The bounds are best possible.