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 established within the class of $1$-triangle graphs for a range of graph-theoretical parameters related to independence and domination. In particular, $\mathrm{NP}$-completeness is established for the minimum perfect neighborhood set problem in the class of all graphs. Bibliogr. 20.