Bounds on the connectivity of iterated line graphs

Yehong Shao


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 K3}, where a divalent path is a path whose internal vertices have degree two in G. Let G be a graph and Ln(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 K1, 3, with l(G)=l ≥ 1. We prove that (i) for integers s ≥ 1, κe(Ll + s(G)) ≥ 2s + 2; (ii) for integers s ≥ 2, κ(Ll + s(G)) ≥ 2s − 1 + 2. The bounds are best possible.


line graphs; iterated line graphs; essential edge connectivity; vertex connectivity

Full Text:




J.A. Bondy and U.S.R. Murty, Graph theory with applications, Macmillan, London and Elsevier, New York, 1976.

R.L. Hemminger and L.W. Beineke, Line Graphs and Line Digraphs, in L.W. Beineke and R.J. Wilson, ed., Selected Topics in Graph Theory, Academic Press, New York, 1978, pp. 271-305.

Y. Shao, Connectivity of iterated line graphs, Discrete Applied Mathematics 158 (2010), 2081-2087.

Y. Shao, Essential edge connectivity of line graphs, Discrete Math. 341 (2018), 3441-3446.

L. Zhang, E. Eschen, H.J. Lai, and Y. Shao, The s-hamiltonian index, Discrete Math. 308 (2008), 4779-4785.

L. Zhang, Y. Shao, G. Chen, X. Xu, and J. Zhou, s-vertex pancyclic index, Graphs and Combinatorics 28 (2012), 393-406.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats