Article ID Journal Published Year Pages File Type
4651194 Discrete Mathematics 2006 4 Pages PDF
Abstract

We prove that for every graph H   with the minimum degree δ⩾5δ⩾5, the third iterated line graph L3(H)L3(H) of H   contains Kδ⌊δ-1⌋ as a minor. Using this fact we prove that if G   is a connected graph distinct from a path, then there is a number kGkG such that for every i⩾kGi⩾kG the i-iterated line graph of G   is 12δ(Li(G))-linked. Since the degree of Li(G)Li(G) is even, the result is best possible.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,