Hamiltonian Connected Line Graphs

Let \(G\) be a simple graph with \(n\) vertices. Let \(L(G)\) denote the line graph of \(G\). We show that if \(\kappa'(G) > 2\) and if for every pair of nonadjacent vertices \(v,u \in V(G)\), \(d(v) + d(u) > \frac{2n}{3} – 2\), then for any pair of vertices \(e, e’ \in V(L(G))\), either \(L(G)\) has a Hamilton \((e, e’)\)-path, or \(\{e, e’\}\) is a vertex-cut of \(L(G)\). When \(G\) is a triangle-free graph, this bound can be reduced to \(\frac{n}{3}\). These bounds are all best possible and they partially improve prior results in [J.Graph Theory 10(1986),411-425] and [Discrete Math.76(1989)95-116].