Some results on multithreshold graphs
share
Jamison and Sprague defined a graph G to be a k-threshold graph with thresholds θ_1 , ..., θ_k (strictly increasing) if one can assign real numbers (r_v)_v ∈ V(G), called ranks, such that for every pair of vertices v,w, we have vw ∈ E(G) if and only if the inequality θ_i ≤ r_v + r_w holds for an odd number of indices i. When k=1 or k=2, the precise choice of thresholds θ_1, ..., θ_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 ≥ 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.
READ FULL TEXT