Some Bounds on the Threshold Dimension of Graphs

Abstract

A graph $G$ on $n$ vertices is a threshold graph if there exist real numbers $a_1,a_2, \ldots,$ $a_n$ and $b$ such that the zero-one solutions of the linear inequality $$\sum \limits_{i=1}^n a_i x_i \leq b$$ are exactly the characteristic vectors of the cliques of $G$.

The threshold dimension of a graph $G$ is the minimum number of threshold graphs whose intersection yields $G$. We give tight or nearly tight upper bounds for the threshold dimension of a graph in terms of various graph parameters including treewidth, maximum degree, degeneracy, number of vertices, and vertex cover number. We also study threshold dimension of random graphs and graphs with high girth.