1-Triangle graphs and perfect neighborhood sets
- Авторлар: Irzhavskii P.1, Kartynnik Y.1, Orlovich Y.1
-
Мекемелер:
- Belarusian State University
- Шығарылым: Том 11, № 1 (2017)
- Беттер: 58-69
- Бөлім: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/212591
- DOI: https://doi.org/10.1134/S1990478917010070
- ID: 212591
Дәйексөз келтіру
Аннотация
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.
Негізгі сөздер
Авторлар туралы
P. Irzhavskii
Belarusian State University
Хат алмасуға жауапты Автор.
Email: irzhavski@bsu.by
Белоруссия, pr. Nezavisimosti 4, Minsk, 220030
Yu. Kartynnik
Belarusian State University
Email: irzhavski@bsu.by
Белоруссия, pr. Nezavisimosti 4, Minsk, 220030
Yu. Orlovich
Belarusian State University
Email: irzhavski@bsu.by
Белоруссия, pr. Nezavisimosti 4, Minsk, 220030