A note on the threshold numbers of cycles

Abstract

A graph $G=(V,E)$ is said to be a \textit{$k$-threshold graph} with \textit{thresholds} ${\theta }_1<{\theta }_2<...<{\theta }_k$ if there is a map $r:V⟶\mathbb{R}$ such that $uv\in E$ if and only if ${\theta }_i\le r(u)+r(v)$ holds for an odd number of $i\in [k]$. The \textit{threshold number} of $G$, denoted by $\Theta (G)$, is the smallest positive integer $k$ such that $G$ is a $k$-threshold graph. In this paper, we determine the exact threshold numbers of cycles by proving \[ Θ(C_n)=\begin{cases} 1 & if\ n=3, 2 & if\ n=4, 4 & if\ n\ge 5, \end{cases} \] where $C_n$ is the cycle with $n$ vertices.

arXiv commentmore succinct; v2: corrected a mistake, made some minor modifications, added some references