Connectivity of iterated line graphs Original Research Article

In this paper we present lower bounds for the connectivity of the i-iterated line graph Li(G) of a graph G. We prove that if G is a connected regular graph and i⩾5, then the connectivity of Li(G) is equal to the degree of Li(G), that is, the connectivity of Li(G) attains its theoretical maximum (we remark that the bound on i is best possible). Moreover, if a hypothesis on the growth of the minimum degree of the i-iterated line graph is true, then an analogous result is true for an arbitrary graph G if i is sufficiently large.