Threshold characterization of graphs with dilworth number two
C. Benzaken, P. L. Hammer, D. de Werra · Journal of Graph Theory · 1985
Abstract A graph with nodes 1, …, n is a threshold signed graph if one can find two positive real numbers S, T and real numbers a1, …, an associated with the vertices in such a way that i, j are linked iff either |ai + aj| ≥ S or |ai ‐ aj| ≥ T. Such graphs generalize threshold graphs. It is shown that these graphs are precisely the graphs with Dilworth number at most two (the Dilworth number is the maximum number of pairwise incomparable vertices in the vicinal preorder). Some other properties of this subclass of perfect graphs are also presented. The graphs considered in this paper are finite simple graphs G = (V, E), where V is the vertex set of G and E a subset of pairs of G. For x V, N(x) denotes the neighbor set of x: N(x) = {y | {x, y} E}.