Hamiltonian Connected Line Graphs

Abstract

Let $G$ be a simple graph with $n$ vertices. Let $L(G)$ denote the line graph of $G$. We show that if ${\kappa }^{\prime }(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^{\prime }\in V(L(G))$, either $L(G)$ has a Hamilton $(e,e^{\prime })$-path, or $\{e,e^{\prime }\}$ 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].