On the Hamiltonicity, traceability and toughness of complements of line graphs

A coline graph $\text{co}(G)$ of a graph $G$ is the graph with vertex set $E(G)$ for which two vertices $e$ and $e'$ of $\text{co}(G)$ are adjacent if and only if they are not adjacent as edges in $G$. A graph $G$ is tough if the number of connected components of $G-S$ is at most $|S|$ for all cut sets $S$. Wu and Meng, and Liu independently gave similar characterisations of coline graphs that are Hamiltonian. In this paper we give an alternate proof of Wu and Meng's and Liu's results using the longest cycle method. We in fact prove the following reformulation of their results. A tough coline graph $\text{co}(G)$ is Hamiltonian unless $G$ is one of four examples, one of which is $K_5$, since $\text{co}(K_5)$ is the Petersen graph. Characterisations of tough coline graphs and of coline graphs that contain a Hamiltonian path are also given.