Geodesic
$1$-Triangle graphs and perfect neighborhood sets
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 56-80

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: triangle graph, edge-simplicial graph, characterization, perfect neighborhood set, $\mathrm{NP}$-completeness. 
@article{DA_2017_24_1_a3,
     author = {P. A. Irzhavskii and Yu. A. Kartynnik and Yu. L. Orlovich},
     title = {$1${-Triangle} graphs and perfect neighborhood sets},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {56--80},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_1_a3/}
}
TY  - JOUR
AU  - P. A. Irzhavskii
AU  - Yu. A. Kartynnik
AU  - Yu. L. Orlovich
TI  - $1$-Triangle graphs and perfect neighborhood sets
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 56
EP  - 80
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_1_a3/
LA  - ru
ID  - DA_2017_24_1_a3
ER  - 
%0 Journal Article
%A P. A. Irzhavskii
%A Yu. A. Kartynnik
%A Yu. L. Orlovich
%T $1$-Triangle graphs and perfect neighborhood sets
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 56-80
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_1_a3/
%G ru
%F DA_2017_24_1_a3
P. A. Irzhavskii; Yu. A. Kartynnik; Yu. L. Orlovich. $1$-Triangle graphs and perfect neighborhood sets. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 1, pp. 56-80. http://geodesic.mathdoc.fr/item/DA_2017_24_1_a3/