zbMATH — the first resource for mathematics

Connectivity of iterated line graphs. (English) Zbl 1215.05097
Summary: Let \(k\geq 0\) be an integer and \(L^k(G)\) be the \(k\)th iterated line graph of a graph \(G\). Niepel and Knor proved that if \(G\) is a 4-connected graph, then \(\kappa (L^{2}(G))\geq 4\delta (G) - 6\). We show that the connectivity of \(G\) can be relaxed. In fact, we prove in this note that if \(G\) is an essentially 4-edge-connected and 3-connected graph, then \(\kappa (L^{2}(G))\geq 4\delta (G) - 6\). Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.

05C40 Connectivity
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan London, Elsevier, New York · Zbl 1134.05001
[2] Chartrand, G.; Stewart, M.J., The connectivity of line graphs, Math. ann., 182, 170-174, (1969) · Zbl 0167.52203
[3] Knor, M.; Niepel, L’., Connectivity of iterated line graphs, Discrete appl. math., 125, 255-266, (2003) · Zbl 1009.05086
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.