Connectivity of iterated line graphs

https://doi.org/10.1016/S0166-218X(02)00197-XGet rights and content
Under an Elsevier user license
open archive

Abstract

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.

MSC

05C40

Keywords

Vertex-connectivity
Edge-connectivity
Graph dynamics
Line graph

Cited by (0)

1

Supported by VEGA grant 1/6293/99.

2

Supported by Kuwait University grant #SM 02/00.