Bounds on the connectivity of iterated line graphs
Yehong Shao · Electronic Journal of Graph Theory and Applications · 2022
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 3 } , where a divalent path is a path whose internal vertices have degree two in G . Let G be a graph and L n ( 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.