2024/06/20 by Wang, Runze
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2406.13955
A graph G=(V,E) is said to be a k-threshold graph with thresholds θ1<θ2<...<θk if there is a map r: V \longrightarrow ℝ such that uv∈ E if and only if θi≤ r(u)+r(v) holds for an odd number of i∈ [k]. The threshold number of G, denoted by Θ(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 Θ(Cn)=\begincases 1 amp; if n=3, 2 amp; if n=4, 4 amp; if n≥ 5, \endcases where Cn is the cycle with n vertices.