Summary: In this paper we show structural and algorithmic properties on the class of Quasi-Threshold graphs, or QT-graphs for short, and prove necessary and sufficient conditions for a QT-graph to be Hamiltonian. Based on these properties and conditions, we construct an efficient parallel algorithm for finding a Hamiltonian cycle in a QT-graph; for an input graph on \(n\) vertices and m edges, our algorithm takes \(O(\log n)\) time and requires \(O(n+m)\) processors on the CREW PRAM model. In addition, we show that the problem of recognizing whether a QT-graph is a Hamiltonian graph and the problem of computing the Hamiltonian completion number of a non-Hamiltonian QT-graph can also be solved in \(O(\log n)\) time with \(O(n+m)\) processors. Our algorithms rely on \(O(\log n)\)-time parallel algorithms, which we develop here, for constructing tree representations of a QT-graph; we show that a QT-graph \(G\) has a unique tree representation, that is, a tree structure which meets the structural properties of \(G\). We also present parallel algorithms for other optimization problems on QT-graphs which run in \(O(\log n)\) time using a linear number of processors.