zbMATH — the first resource for mathematics

Connectivity of iterated line graphs. (English) Zbl 1009.05086
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.

05C40 Connectivity
Full Text: DOI
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.