omit the subscript. A linear ordering $\prec$ on a set $S$ with $|S| = n$ can be represented by a sequence $\langle s_{1}, s_{2}, \dots, s_{n} \rangle$ of the elements in $S$, in which $s_{i} \prec s_{j}$ if and only if $i< j$. By abusing the notation, we sometimes write ${\prec} = \langle s_{1}, s_{2}, \dots, s_{n} \rangle$.

Double-threshold graphs
-----------------------

A graph $G=(V,E)$ is a *threshold graph* if there exist a vertex-weight function ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and a real number ${\mathtt{lb}}\in {\mathbb{R}}$ with the following property: $$uv \in E \iff {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v).$$ A graph $G=(V,E)$ is a *double-threshold graph* if there exist a vertex-weight function ${\mathtt{w}}\colon V \to {\mathbb{R}}$ and two real numbers ${\mathtt{lb}}, {\mathtt{ub}}\in {\mathbb{R}}$ with the following property: $$uv \in E \iff {\mathtt{lb}}\le {\mathtt{w}}(u) + {\mathtt{w}}(v) \le {\mathtt{ub}}.$$ Then, we say that the double-threshold graph $G$ is *defined* by ${\mathtt{w}}$, ${\mathtt{lb}}$ and ${\mathtt{ub}}$.

The definition of a double-threshold graph can be understood visually in the plane. See [ \[fig:dtg\_example1\]]{} for an example. In the $xy$-plane, we consider the slab defined by $\{(x,y) \mid {\mathtt{lb}}\leq x+y \leq {\mathtt{ub}}\}$ that is illustrated in gray. Then, two vertices $u,v \in V$ are joined by an edge if 