Threshold numbers of some graphs

Abstract

A graph $G=(V,E)$ is called a \emph{$k$-threshold graph} with \emph{thresholds} $\hat{I}{¸}_1<\hat{I}{¸}_2<...<\hat{I}{¸}_k$ if we can assign a real number $r(v)$ to each vertex $v\in V$, such that for any $u,v\in V$, we have $uv\in E$ if and only if $r(u)+r(v)\ge \hat{I}{¸}_i$ holds true for an odd number of elements in $\{\hat{I}{¸}_1,\hat{I}{¸}_2,...,\hat{I}{¸}_k\}$. The smallest integer $k$ such that $G$ is a $k$-threshold graph is called the \emph{threshold number} of $G$. For the complete multipartite graphs and the cluster graphs, Kittipassorn and Sumalroj determined the exact threshold numbers of $K_{n\times 3}$ and $n{K}_3$. In this paper, first we determine the threshold numbers of some path-related graphs, including linear forests, ladders, and tents. Then, on the basis of Kittipassorn and Sumalroj's results, we determine the exact threshold numbers of $K_{n_1\times 1,n_2\times 2,n_3\times 3}$ and $n_1{K}_1\cup n_2{K}_2\cup n_3{K}_3$, which solve a problem proposed by Sumalroj.

title changed, new content added; v2: more succinct