Premium
Threshold characterization of graphs with dilworth number two
Author(s) -
Benzaken C.,
Hammer P. L.,
de Werra D.
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090207
Subject(s) - combinatorics , mathematics , indifference graph , pathwidth , chordal graph , discrete mathematics , 1 planar graph , cograph , clique sum , vertex (graph theory) , metric dimension , graph , line graph
A graph with nodes 1, …, n is a threshold signed graph if one can find two positive real numbers S, T and real numbers a 1 , …, a n associated with the vertices in such a way that i, j are linked iff either | a i + a j | ≥ S or | a i ‐ a j | ≥ 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 }.