Quasi-threshold graphs (Q1923584)

Quasi-threshold graphs are defined recursively by the following rules: (1) \(K_1\) is a quasi-threshold graph, (2) adding a new vertex adjacent to all vertices of a quasi-threshold graph results in a quasi-threshold graph, (3) the disjoint union of two quasi-threshold graphs is a quasi-threshold graph. The paper gives some new equivalent definitions of quasi-threshold graph. From them, linear time recognition algorithms follow. The paper also presents linear time algorithms for the edge domination problem and the bandwidth problem in this class of graphs.