asked for a characterization of star pairwise compatibility graphs. Recently, Xiao and Nagamochi [@XiaoN18] solved the open problem and gave an $O(n^6)$-time algorithm to recognize a star pairwise compatibility graph.

As we will see after the formal definition of double-threshold graphs, the star pairwise compatibility graphs are precisely the double-threshold graphs. Although the pairwise compatibility graphs are rather well studied, we study the double-threshold graphs in the context of threshold graphs and their generalizations. This is because, in our opinion, the double-threshold graphs and techniques used for them are more relevant in that context.

Preliminaries {#sec:preliminaries}
=============

All graphs in this paper are undirected, simple, and finite. A graph $G$ is given by the pair of its vertex set $V$ and its edge set $E$ as $G=(V,E)$. The vertex set and the edge set of $G$ are often denoted by $V(G)$ and $E(G)$, respectively. The *order* of a graph refers to the number of its vertices. For a vertex $v$ in a graph $G = (V,E)$, its *neighborhood* is the set of vertices that are adjacent to $v$, and denoted by $N_{G}(v) = \{ u \mid uv \in E\}$. When the graph $G$ is clear from the context, we often 