Journal of Applied and Industrial Mathematics, 2017, 11:1, 58-69
Volume 24, No 1, 2017, P. 56-80
Keywords: triangle graph, edge-simplicial graph, characterization, perfect neighborhood set, NP-completeness.
Received 16 March 2016
References 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].
 M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 [Russian]. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi,Mir, Moscow, 1982.
 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.
 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].
 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].
 C. Anbeek, D. DeTemple, K. McAvaney, and J. M. Robertson,When are chordal graphs also partition graphs?, Australas. J. Comb., 16, 285–293, 1997.
 B. Bollobás and E. J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, No. 3, 241–249, 1979.
 E. Boros, V. Gurvich, and M. Milanic, On equistable, split, CIS, and related classes of graphs, 2015 (Cornell Univ. Libr. e-Print Archive, arXiv:1505.05683).
 G. A. Cheston, E. O. Hare, S. T. Hedetniemi and R. C. Laskar, Simplicial graphs, Congr. Numerantium, 67, 105–113, 1988.
 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.
 D. DeTemple, F. Harary, and J. M. Robertson, Partition graphs, Soochow J. Math., 13, No. 2, 121–129, 1987.
 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.
 V. Guruswami, C. P. Rangan, M. S. Chang, G. J. Chang, and C. K. Wong, The vertex-disjoint triangles problem, in Graph-Theoretic 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).
 T. Kloks, C.-M. Lee, J. Liu, and H. Müller, On the recognition of general partition graphs, in Graph-Theoretic 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).
 K. McAvaney, J. M. Robertson, and D. DeTemple, A characterization and hereditary properties for partition graphs, Discrete Math., 113, 131–142, 1993.
 Š. Miklavic and M. Milanic, Equistable graphs, general partition graphs, triangle graphs, and graph products, Discrete Appl. Math., 159, No. 11, 1148–1159, 2011.
 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.
 Yu. L. Orlovich and I. E. Zverovich, Independent domination in triangle graphs, Electron. Notes Discrete Math., 28, 341–348, 2007.
 E. Sampathkumar and P. S. Neeralagi, The neighbourhood number of a graph, Indian J. Pure Appl. Math., 16, 126–132, 1985.
 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|