Threshold characterization of graphs with dilworth number two
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.
- Probe threshold and probe trivially perfect graphs
- Perfectness and Dilworth number
- Split graphs of Dilworth number 2
- Intersection graphs of halflines and halfplanes
- A note on perfect orders
- On dynamic threshold graphs and related classes
- Double-threshold permutation graphs
- On pairwise compatibility graphs having Dilworth number k
- On pairwise compatibility graphs having Dilworth number two
- The simple graph threshold number (r,s,a,t) when r 3 is odd and a 2 is even
- Fully dynamically maintaining minimal integral separator for threshold and difference graphs
- Box-threshold graphs
- scientific article; zbMATH DE number 4125434 (Why is no real title available?)
- Corrigendum to: ``On pairwise compatibility graphs having Dilworth number two
- Difference graphs
- Linear-time recognition of double-threshold graphs
- Bipartite bithreshold graphs
- A bound for the Dilworth number
- Vicinal orders of trees
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)