Linkability in iterated line graphs

The authors prove that for every graph \(H\) with minimum degree \(\delta\geq 5\), the third iterated line graph \(L^3(H)\) of \(H\) contains \(K_t\) as a minor, \(t= \delta\cdot\lfloor\sqrt{\delta-1}\rfloor\). Using this statement, the authors prove that if \(G\) is a connected graph distinct from a path, then there is a number \(k_G\) such that for every \(i\geq k_G\) the \(i\)-iterated line graph of \(G\) is \(\frac 12 \delta\cdot(L^i(G))\)-linked. This result is best posible, since the degree of \(L^i(G)\) is even.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Linkability in iterated line graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2488940)