Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 58-69
Volume 24, No 1, 2017, P. 56-80
UDC 519.17
P. A. Irzhavskii, Yu. A. Kartynnik, and Yu. L. Orlovich
1-Triangle graphs and perfect neighborhood sets
Abstract:
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, 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, NP-completeness.
DOI: 10.17377/daio.2017.24.532
Pavel A. Irzhavskii 1
Yury A. Kartynnik 1
Yury L. Orlovich 1
1. Belarusian State University,
4 Nezavisimosti Ave., 220030 Minsk, Belarus
e-mail: irzhavski@bsu.by, kartynnik@bsu.by, orlovich@bsu.by
Received 16 March 2016
Revised 27 June 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 NP-Completeness, 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, Graph-theoretic 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. e-Print 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 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).
[14] 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).
[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.
