Equivalent characterization for threshold graphs one common way of defining threshold graphs $ G=(V,E) $ is given by: G is threshold iff there exists an integer labeling function $ c:V \rightarrow \mathbb{N} $ and an integer threshold $ T \in \mathbb{N} $ such that $ xy \in E \Longleftrightarrow c(x)+c(y)>T $. My question would be: is it really necessary to have the strict inequality? Could we also define it this way: G is threshold iff there exists an integer labeling function $ a:V \rightarrow \mathbb{N} $ and an integer threshold $ S \in \mathbb{N} $ such that $ xy \in E \Longleftrightarrow a(x)+a(y)\ge S $. Or is there some graph that can serve as a counterexample for this "alternative" definition? Thanks a lot.

Certainly those are equivalent. Given a threshold graph by the first definition, we could keep the labeling function $a(x)$ equal to $c(x)$ and define $$S = \min\\{c(x) + c(y) : c(x)+c(y) > T\\}.$$ (Equivalently, this is $\min\\{c(x)+c(y) : xy \in E\\}$.) Then the set of edges defined by the condition $c(x)+c(y) > T$ is the same as the set of edges defined by the condition $a(x)+a(y) \ge S$.

Conversely, given a threshold graph by the second definition, define $c(x) = 2a(x)$ for all $x$ and define $T = 2S-1$. Then the set of edges defined by the condition $c(x) + c(y) > T$ is the same as the set of edges defined by the condition $a(x) + a(y) \ge S$.