INVESTIGADORES
DE CARIA DI FONZO Pablo Jesus
artículos
Título:
On the recognition of neighborhood inclusion posets
Autor/es:
DE CARIA, PABLO
Revista:
Electronic Notes in Discrete Mathematics
Editorial:
Elsevier B.V.
Referencias:
Año: 2017 vol. 62 p. 285 - 290
ISSN:
1571-0653
Resumen:
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.
