Quasi-threshold graphs
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.
scientific article; zbMATH DE number 933099
scientific article