Multithreshold multipartite graphs

作者：Chen, Guantao; Hao, Yanli^*

来源：Journal of Graph Theory, 2022, 100(4): 727-732.

DOI：10.1002/jgt.22805

• complete multipartite graphs
• graph representation
• threshold graphs
• threshold numbers
• vertex ranks

We call a graph G a k-threshold graph if there are k distinct real numbers theta(1), theta(2), horizontal ellipsis ,theta(k) and a mapping r : V(G)-> R such that for any two vertices u,v is an element of V(G), we have that uv is an element of E(G) if and only if there are odd numbers theta(i) such that theta i <= r(u) + r(v). The least integer k such that G is a k-threshold graph is called a threshold number of G, and denoted by Theta(G). The well-known family of threshold graphs is a set of graphs G with Theta(G) <= 1. Jamison and Sprague introduced the concept of k-threshold graph, and proved that Theta(G) exists for every graph G. They further obtained a number of interesting results on Theta(G). In addition, they also proposed several unsolved problems and conjectures, including the following two. @@@ Problem: Determine the exact threshold numbers of the complete multipartite graphs. @@@ Conjecture: For all even n >= 2 , there is a graph G with Theta(G) = n and Theta (G(c)) = n + 1. This is equivalent to that for all odd