On the inverse problem for integer indices in threshold graphs

The inverse problem for integer indices investigates the existence of graphs having a prescribed integer as their indices. In this paper, we address this problem within the class of threshold graphs, seeking solutions distinct from the trivial complete graph. For this, we develop a linear-time algorithm that, given a threshold graph (encoded by its cotree parameters) together with an integer k , decides whether k is the index of that specific graph. Furthermore, we prove that every integer k ≥ 3 k ≥ 3 is realizable within the classes of star and pineapple graphs. These results demonstrate that threshold graphs provide a non-trivial framework for integer spectral constraints, offering a constructive counterpart to recent findings on forbidden spectral intervals.