1-Triangle graphs and perfect neighborhood sets

Abstract

A graph is called a 1-triangle if, for its every maximal independent set I, every edge of this graph with both endvertices not belonging to I is contained exactly in one triangle with a vertex of I. We obtain a characterization of 1-triangle graphs which implies a polynomial time recognition algorithm. Computational complexity is establishedwithin the class of 1-triangle graphs for a range of graph-theoretical parameters related to independence and domination. In particular, NP-completeness is established for the minimum perfect neighborhood set problem in the class of all graphs.