04006296

a

04006296 Bauer, Douglas A note on degree conditions for Hamiltonian cycles in line graphs. Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 49, 11-18 (1985). 1985 EN vertex degrees Hamiltonian cycle Zbl 0619.00006 [For the entire collection see Zbl 0619.00006.] We consider the problem of finding best possible sufficient conditions on the vertex degrees of a graph G to insure the existence of a Hamiltonian cycle in its line graph L(G). Specifically, we seek the largest positive integer g(k) such that if G is a 2-connected graph having minimum degree at least k and at most g(k) vertices then L(G) is Hamiltonian. We prove that $g(3)=13$ and that $g(k)\le 5k+4$ for $k\ge 4$.