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/

[1] C. Bergé, Théorie des graphes et ses applications, Dunod, Paris, 1958 (French) | MR

[2] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | Zbl

[3] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR

[4] Yu. A. Kartynnik, Yu. L. Orlovich, “Domination triangle graphs and upper bound graphs”, Dokl. Nats. Akad. Nauk Belarusi, 58:1 (2014), 16–25 (Russian)

[5] Yu. L. Orlovich, V. S. Gordon, J. Błażewicz, I. E. Zverovich, G. Finke, “Independent dominating and neighborhood sets in triangular graphs”, Dokl. Nats. Akad. Nauk Belarusi, 53:1 (2009), 39–44 (Russian)

[6] Anbeek C., DeTemple D., McAvaney K. L., Robertson J. M., When are chordal graphs also partition graphs?, Australas. J. Comb., 16 (1997), 285–293 | MR | Zbl

[7] Bollobaś B., Cockayne E. J., “Graph-theoretic parameters concerning domination, independence, and irredundance”, J. Graph Theory, 3:3 (1979), 241–249 | DOI | MR | Zbl

[8] Boros E., Gurvich V., Milanic̆ M., On equistable, split, CIS, and related classes of graphs, 2015, arXiv: 1505.05683 | MR

[9] Cheston G. A., Hare E. O., Hedetniemi S. T., Laskar R. C., “Simplicial graphs”, Congr. Numerantium, 67 (1988), 105–113 | MR | Zbl

[10] Cheston G. A., Jap T. S., “A survey of the algorithmic properties of simplicial, upper bound and middle graphs”, J. Graph Algorithms Appl., 10:2 (2006), 159–190 | DOI | MR | Zbl

[11] DeTemple D., Harary F., Robertson J. M., “Partition graphs”, Soochow J. Math., 13:2 (1987), 121–129 | MR | Zbl

[12] DeTemple D., Robertson J. M., “Graphs associated with triangulations of lattice polygons”, J. Austr. Math. Soc., Ser. A, 47:3 (1989), 391–398 | DOI | MR | Zbl

[13] Guruswami V., Rangan C. P., Chang M. S., Chang G. J., Wong C. K., “The vertex-disjoint triangles problem”, Graph-Theoretic Concepts in Computer Science, Proc. 24th Int. Workshop (Smolenice Castle, Slovak Rep., June 18–20, 1998), Lect. Notes Comput. Sci., 1517, Springer, Heidelberg, 1998, 26–37 | DOI | MR | Zbl

[14] Kloks T., Lee C.-M., Liu J., Müller H., “On the recognition of general partition graphs”, Graph-Theoretic Concepts in Computer Science, Proc. 29th Int. Workshop (Elspeet, The Netherlands, June 19–21, 2003), Lect. Notes Comput. Sci., 2880, Springer, Heidelberg, 2003, 273–283 | DOI | Zbl

[15] McAvaney K., Robertson J., DeTemple D., “A characterization and hereditary properties for partition graphs”, Discrete Math., 113:1 (1993), 131–142 | DOI | MR | Zbl

[16] Miklavic̆ Š., Milanic̆ M., “Equistable graphs, general partition graphs, triangle graphs, and graph products”, Discrete Appl. Math., 159:11 (2011), 1148–1159 | DOI | MR | Zbl

[17] Orlovich Yu. L., Błażewicz J., Dolgui A., Finke G., Gordon V., “On the complexity of the independent set problem in triangle graphs”, Discrete Math., 311:16 (2011), 1670–1680 | DOI | MR | Zbl

[18] Orlovich Yu. L., Zverovich I. E., “Independent domination in triangle graphs”, Electron. Notes Discrete Math., 28 (2007), 341–348 | DOI | MR | Zbl

[19] Sampathkumar E., Neeralagi P. S., “The neighbourhood number of a graph”, Indian J. Pure Appl. Math., 16 (1985), 126–132 | MR | Zbl

[20] Sampathkumar E., Neeralagi P. S., “Independent, perfect and connected neighbourhood numbers of a graph”, J. Comb. Inf. Syst. Sci., 19:3–4 (1994), 139–145 | MR | Zbl