1-Triangle graphs and perfect neighborhood sets |
| |
Authors: | P A Irzhavskii Yu A Kartynnik Yu L Orlovich |
| |
Institution: | 1.Belarusian State University,Minsk,Belarus |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|