|
|||||
|
|
Linkability in iterated line graphs |
|
| Authors: | Thomas Böhme |
| Institution: | a Fak. für Mathematik und Naturwissenschaften, Technische Universität Ilmenau, Postfach 100565, 98684 Ilmenau, Deutschland b Faculty of Civil Engineering, Department of Mathematics, Slovak University of Technology, Radlinského 11, 813 68 Bratislava, Slovakia c Faculty of Science, Department of Mathematics & Computer Science, Kuwait University, P.O. Box 5969 Safat 13060, Kuwait |
| Abstract: | We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L3(H) of H contains  as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number kG such that for every i?kG the i-iterated line graph of G is  -linked. Since the degree of Li(G) is even, the result is best possible. |
| Keywords: | Iterated line graph _method=retrieve& _eid=1-s2 0-S0012365X06000616& _mathId=si8 gif& _pii=S0012365X06000616& _issn=0012365X& _acct=C000053510& _version=1& _userid=1524097& md5=97b548451ef9c40f5ed32cba09874cc0')" style="cursor:pointer k-linked graph" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">k-linked graph Connectivity Graph dynamics Minor |
| 本文献已被 ScienceDirect 等数据库收录！ | |