Threshold characterization of graphs with dilworth number two

From MaRDI portal





A threshold signed graph is a graph whose vertices \(1,\ldots,n\) are labelled by the real numbers \(a_ 1,\ldots,a_ n\) and in which two vertices i, j are adjacent if and only if either \(| a_ i+a_ j| \geq S\), or \(| a_ i-a_ j| \geq T\), where S, T are given positive real numbers (called thresholds). The vicinal preorder \(=^{\prec}_{G}\) on the vertex set of a graph G is defined in such a way that \(x=^{\prec}_{G}y\) if and only if N(x)\(\subseteq N(y)\cup \{y\}\), where N(x), N(y) are the sets of vertices adjacent in G to x or y respectively. The maximum number of pairwise incomparable vertices in the vicinal preorder in G is called the Dilworth number of G. The main theorem states that a graph G is a threshold signed graph if and only if its Dilworth number is at most 2. A corollary of this theorem states that the class of threshold signed graphs is closed under complementation. Further properties of these graphs are described and forbidden induced subgraphs for them are listed.











This page was built for publication: Threshold characterization of graphs with dilworth number two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3708054)