ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:1, 5869 

Volume 24, No 1, 2017, P. 5680 UDC 519.17
Keywords: triangle graph, edgesimplicial graph, characterization, perfect neighborhood set, NPcompleteness. DOI: 10.17377/daio.2017.24.532 Pavel A. Irzhavskii ^{1} Received 16 March 2016 References[1] C. Bergé, Théorie des graphes et ses applications, Dunod, Paris, 1958 [French]. Translated under the title Teoriya grafov i eyo primeneniya, Izd. Inostr. Lit., Moscow, 1962 [Russian].[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979 [Russian]. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi,Mir, Moscow, 1982. [3] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, Moscow, 1990 [Russian]. Translated under the title Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994. [4] Yu. A. Kartynnik and Yu. L. Orlovich, Domination triangle graphs and upper bound graphs, Dokl. Nats. Akad. Nauk Belarusi, 58, No. 1, 16–25, 2014 [Russian]. [5] Yu. L. Orlovich, V. S. Gordon, J. Blazewicz, I. E. Zverovich, and G. Finke, Independent dominating and neighborhood sets in triangular graphs, Dokl. Nats. Akad. Nauk Belarusi, 53, No. 1, 39–44, 2009 [Russian]. [6] C. Anbeek, D. DeTemple, K. McAvaney, and J. M. Robertson,When are chordal graphs also partition graphs?, Australas. J. Comb., 16, 285–293, 1997. [7] B. Bollobás and E. J. Cockayne, Graphtheoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, No. 3, 241–249, 1979. [8] E. Boros, V. Gurvich, and M. Milanic, On equistable, split, CIS, and related classes of graphs, 2015 (Cornell Univ. Libr. ePrint Archive, arXiv:1505.05683). [9] G. A. Cheston, E. O. Hare, S. T. Hedetniemi and R. C. Laskar, Simplicial graphs, Congr. Numerantium, 67, 105–113, 1988. [10] G. A. Cheston and T. S. Jap, A survey of the algorithmic properties of simplicial, upper bound and middle graphs, J. Graph Algorithms Appl., 10, No. 2, 159–190, 2006. [11] D. DeTemple, F. Harary, and J. M. Robertson, Partition graphs, Soochow J. Math., 13, No. 2, 121–129, 1987. [12] D. DeTemple and J. M. Robertson, Graphs associated with triangulations of lattice polygons, J. Aust. Math. Soc., Ser. A, 47, No. 3, 391–398, 1989. [13] V. Guruswami, C. P. Rangan, M. S. Chang, G. J. Chang, and C. K. Wong, The vertexdisjoint triangles problem, in GraphTheoretic Concepts in Computer Science (Proc. 24th Int. Workshop, Smolenice Castle, Slovak Republic, June 18–20, 1998), pp. 26–37, Springer, Heidelberg, 1998 (Lect. Notes Comput. Sci., Vol. 1517). [14] T. Kloks, C.M. Lee, J. Liu, and H. Müller, On the recognition of general partition graphs, in GraphTheoretic Concepts in Computer Science (Proc. 29th Int. Workshop, Elspeet, The Netherlands, June 19–21, 2003), pp. 273–283, Springer, Heidelberg, 2003 (Lect. Notes Comput. Sci., Vol. 2880). [15] K. McAvaney, J. M. Robertson, and D. DeTemple, A characterization and hereditary properties for partition graphs, Discrete Math., 113, 131–142, 1993. [16] Š. Miklavic and M. Milanic, Equistable graphs, general partition graphs, triangle graphs, and graph products, Discrete Appl. Math., 159, No. 11, 1148–1159, 2011. [17] Yu. L. Orlovich, J. Blazewicz, A. Dolgui, G. Finke, and V. S. Gordon, On the complexity of the independent set problem in triangle graphs, Discrete Math., 311, No. 16, 1670–1680, 2011. [18] Yu. L. Orlovich and I. E. Zverovich, Independent domination in triangle graphs, Electron. Notes Discrete Math., 28, 341–348, 2007. [19] E. Sampathkumar and P. S. Neeralagi, The neighbourhood number of a graph, Indian J. Pure Appl. Math., 16, 126–132, 1985. [20] E. Sampathkumar and P. S. Neeralagi, Independent, perfect and connected neighbourhood numbers of a graph, J. Comb. Inf. Syst. Sci., 19, No. 3–4, 139–145, 1994. 

© Sobolev Institute of Mathematics, 2015  