Double-threshold graphs are defined in terms of two real thresholds that break the real line into three regions, alternating as NO-YES-NO. If real ranks can be assigned to the vertices of a graph in such a way that two vertices are adjacent iff the sum of their ranks lies in the YES region, then that graph is a double-threshold graph with respect to the given set of thresholds. We demonstrate that all double-threshold graphs are permutation graphs. As a partial converse, we show that every bipartite permutation graph has a balanced double-threshold representation. That is, the vertices with negative rank form one part of the bipartition, those with positive rank the other part.
展开▼
