Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876226 | Theoretical Computer Science | 2014 | 7 Pages |
Abstract
It is known that LPGâ©mLPG is not empty and that threshold graphs, i.e. Dilworth one graphs, are contained in it. In this paper we prove that Dilworth two graphs belong to the set LPGâ©mLPG, too. Our proof is constructive since we show how to compute all the parameters T, w, dmax and dmin exploiting the usual representation of Dilworth two graphs in terms of node weight function and thresholds. For graphs with Dilworth number two that are also split graphs, i.e. split permutation graphs, we provide another way to compute T, w, dmin and dmax when these graphs are given in terms of their intersection model.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T. Calamoneri, R. Petreschi,