Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651194 | Discrete Mathematics | 2006 | 4 Pages |
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
Thomas Böhme, Martin Knor, L’udovít Niepel,