Connectivity of iterated line graphs. (English) Zbl 1009.05086

Knor, Martin; Niepel, L’udovít

Discrete Appl. Math. 125, No. 2-3, 255-266 (2003).

Summary: We present lower bounds for the connectivity of the \(i\)-iterated line graph \(L^i(G)\) of a graph \(G\). We prove that if \(G\) is a connected regular graph and \(i\geqslant 5\), then the connectivity of \(L^i(G)\) is equal to the degree of \(L^i(G)\), that is, the connectivity of \(L^i(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

Connectivity

Keywords:

vertex-connectivity; edge-connectivity; graph dynamics; line graph

References:

[1]	G. Chartrand, F. Harary, Graphs with prescribed connectivities, Theory of Graphs, Akademiai Kiado, Budapest, 1968, pp. 61-63. · Zbl 0186.27503
[2]	Chartrand, G.; Stewart, M.J., The connectivity of line-graphs, Math. ann., 182, 170-174, (1969) · Zbl 0167.52203
[3]	Fàbrega, J.; Fiol, M.A., Maximally connected digraphs, J. graph theory, 13, 6, 657-668, (1989) · Zbl 0688.05029
[4]	Harary, F., Graph theory, (1969), Addison-Wesley London · Zbl 0797.05064
[5]	Hartke, S.G.; Higgins, A.W., Maximum degree growth of the iterated line graph, Electron. J. comb., 6, 1, R28, (1999), (Research paper, 9p.) · Zbl 0920.05058
[6]	Knor, M.; Niepel, L’.; Šoltés, L’., Centers in iterated line graphs, Acta math. univ. Comenian, LXI, 237-241, (1992) · Zbl 0821.05022
[7]	Niepel, L’.; Knor, M.; Šoltés, L’., Distances in iterated line graphs, Ars combin., 43, 193-202, (1996) · Zbl 0881.05059
[8]	L. Xiong, Z. Liu, Hamiltonian iterated line graphs Discrete Math., to appear. · Zbl 1027.05055