Jamison and Sprague defined multithreshold graphs as a generalization of the well-studied threshold graphs. A graph $G=(V,E)$ is called a k-threshold graph with thresholds θ₁<θ₂<...<θₖ if we can assign a real number $r(v)$ to each vertex v∈ V such that for any two vertices u,v∈ V, we have uv∈ E if and only if $r(u)+r(v)$ is greater than or equal to an odd number of θ₁,θ₂,...,θₖ. The smallest integer k such that G is a k-threshold graph is called the threshold number of G. For the complete multipartite graphs and the cluster graphs, Chen and Hao determined the exact threshold numbers of those graphs with each part/cluster not being small; Puleo proved a lower bound on the threshold numbers of nK₃; Kittipassorn and Sumalroj further determined the exact threshold numbers of Kn× 3, nK₃, Kn× 4, and nK₄. On the basis of Kittipassorn and Sumalroj's results, we determine the exact threshold numbers of Kn₁× 1, n₂× 2, n₃× 3 and n₁ K₁∪ n₂ K₂∪ n₃ K₃, which solve a problem proposed by Sumalroj.
No takes yet. Share an insight, caveat, or question.
Runze Wang (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: