1-Triangle graphs and perfect neighborhood sets
- Authors: Irzhavskii P.A.1, Kartynnik Y.A.1, Orlovich Y.L.1
-
Affiliations:
- Belarusian State University
- Issue: Vol 11, No 1 (2017)
- Pages: 58-69
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212591
- DOI: https://doi.org/10.1134/S1990478917010070
- ID: 212591
Cite item
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.
About the authors
P. A. Irzhavskii
Belarusian State University
Author for correspondence.
Email: irzhavski@bsu.by
Belarus, pr. Nezavisimosti 4, Minsk, 220030
Yu. A. Kartynnik
Belarusian State University
Email: irzhavski@bsu.by
Belarus, pr. Nezavisimosti 4, Minsk, 220030
Yu. L. Orlovich
Belarusian State University
Email: irzhavski@bsu.by
Belarus, pr. Nezavisimosti 4, Minsk, 220030