structures and applications in many areas [@MahadevP1995; @Golumbic04]. In particular, the edge-intersections of two threshold graphs, and their complements (i.e., the union of two threshold graphs) have attracted several researchers in the past, and recognition algorithms with running time $O(n^5)$ by Ma [@Ma93], $O(n^4)$ by Raschle and Simon [@RaschleS95], and $O(n^3)$ by Sterbini and Raschle [@SterbiniR98] have been developed, where $n$ is the number of vertices.

In this paper, we study the class of double-threshold graphs, which is a proper generalization of threshold graphs and a proper specialization of the graphs that are edge-intersections of two threshold graphs. A graph is a *double-threshold graph* if there exist a vertex-weight function and two real numbers called lower and upper bounds of weight such that two vertices are adjacent if and only if their weight sum is at least the lower bound and at most the upper bound. To the best of our knowledge, this natural generalization of threshold graphs was not studied until quite recently. In 2018, Xiao and Nagamochi [@XiaoN18] studied this graph class under the different name of “star pairwise compatibility graphs” and presented an $O(n^6)$-time recognition algorithm.

Our main result is to give a new characterization of double-threshold 