Some results on multithreshold graphs

Abstract

Jamison and Sprague defined a graph $G$ to be a $k$-threshold graph with thresholds ${\theta }_1,\dots ,{\theta }_k$ (strictly increasing) if one can assign real numbers $(r_v{)}_{v\in V(G)}$, called ranks, such that for every pair of vertices $v,w$, we have $vw\in E(G)$ if and only if the inequality ${\theta }_i\le r_v+r_w$ holds for an odd number of indices $i$. When $k=1$ or $k=2$, the precise choice of thresholds ${\theta }_1,\dots ,{\theta }_k$ does not matter, as a suitable transformation of the ranks transforms a representation with one choice of thresholds into a representation with any other choice of thresholds. Jamison asked whether this remained true for $k\ge 3$ or whether different thresholds define different classes of graphs for such $k$, offering $50 for a solution of the problem. Letting $C_t$ for $t>1$ denote the class of $3$-threshold graphs with thresholds $-1,1,t$, we prove that there are infinitely many distinct classes $C_t$, answering Jamison's question. We also consider some other problems on multithreshold graphs, some of which remain open.

6 pages, 1 figure