Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903528 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
Abstract
Let G be a simple graph. When we order the different closed neighborhoods of G by inclusion, the resulting poset is called the neighborhood inclusion poset. In this paper, we show that the problem of determining whether a poset is a neighborhood inclusion poset is NP-complete. We also apply this result to prove the NP-completeness of another problem about clique trees of chordal graphs and compatible trees of dually chordal graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pablo De Caria,