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$.