danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-176Research ArticleМАТЕМАТИКАMATHEMATICSДОМИНАНТНО-ТРЕУГОЛЬНЫЕ ГРАФЫ И ГРАФЫ ВЕРХНИХ ГРАНИЦDOMINATION TRIANGLE GRAPHS AND UPPER BOUND GRAPHSКАРТЫННИКЮ. А.KARTYNNIKYu. A.kartynnik@gmail.comОРЛОВИЧЮ. Л.ORLOVICHYu. L.orlovich@bsu.byБелорусский государственный университет, МинскBelarus2014080620165811625Copyright © КАРТЫННИК Ю.А., ОРЛОВИЧ Ю.Л., 20162016КАРТЫННИК Ю.А., ОРЛОВИЧ Ю.Л.KARTYNNIK Y.A., ORLOVICH Y.L.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/176

В работе вводится и изучается собственный подкласс треугольных графов, а именно доминантно-треугольные графы. Граф G называется доминантно-треугольным, если для любого минимального доминирующего множества D графа G и любых смежных вершин u и v, не входящих в D, существует вершина w є D, одновременно смежная с u и v, т. е. множество {u, v, w} порождает треугольник в графе G. Получен ряд характеризаций класса доминантно-треугольных графов, которые, в частности, указывают на совпадение этого класса графов с хорошо известным классом графов верхних границ и классом ирридантно-треугольных графов. Установлена вычислительная сложность и сложность аппроксимации в классе доминантно-треугольных графов некоторых теоретико-графовых параметров, родственных классическим числам независимости и доминирования.

In this article we introduce and study a proper subclass of triangle graphs, namely, the domination triangle graphs. A graph G is called a domination triangle graph if for every minimal dominating set D of G and any adjacent vertices u and v not contained in D, there exists a vertex w є D such that the set {u, v, w} induces a triangle in G. We propose a number of characterizations of domination triangle graphs which show in particular that this class of graphs coincides with a well-known class of upper bound graphs and a class of irredundance triangle graphs. We establish the computational complexity and the complexity of approximation for some independence and domination-related graph-theoretical parameters within domination triangle graphs.

ReferencesOrlovich Y., Zverovich I. // Electronic Notes in Discrete Math. 2007. Vol. 28. P. 341–348.Orlovich Y., Zverovich I. // Electronic Notes in Discrete Math. 2007. Vol. 28. P. 341–348.McAvaney K., Robertson J., De Temple D. // Discrete Math. 1993. Vol. 113, N 1–3. P. 131–142.McAvaney K., Robertson J., De Temple D. // Discrete Math. 1993. Vol. 113, N 1–3. P. 131–142.Anbeek C., De Temple D., McAvaney K., Robertson J. // Australas. J. Comb. 1997. Vol. 16. P. 285–293.Anbeek C., De Temple D., McAvaney K., Robertson J. // Australas. J. Comb. 1997. Vol. 16. P. 285–293.Kloks T., Lee C.-M., Liu J., Müller H. // Lect. Notes Comput. Sci. 2003. Vol. 2880. P. 273–283.Kloks T., Lee C.-M., Liu J., Müller H. // Lect. Notes Comput. Sci. 2003. Vol. 2880. P. 273–283.Орлович Ю. Л., Гордон В. С., Блажевич Я. и др. // Докл. НАН Беларуси. 2009. Т. 53, № 1. С. 39–44.Орлович Ю. Л., Гордон В. С., Блажевич Я. и др. // Докл. НАН Беларуси. 2009. Т. 53, № 1. С. 39–44.Miklavič Š., Milanič M. // Discrete Appl. Math. 2011. Vol. 159, N 11. P. 1148–1159.Miklavič Š., Milanič M. // Discrete Appl. Math. 2011. Vol. 159, N 11. P. 1148–1159.Orlovich Y., Blazewicz J., Dolgui A. et al. // Discrete Math. 2011. Vol. 311, N 16. P. 1670–1680.Orlovich Y., Blazewicz J., Dolgui A. et al. // Discrete Math. 2011. Vol. 311, N 16. P. 1670–1680.Levit V. E., Milanič M. // Discrete Appl. Math. 2014. Vol. 165. P. 205–212.Levit V. E., Milanič M. // Discrete Appl. Math. 2014. Vol. 165. P. 205–212.Payan C. // Discrete Math. 1980. Vol. 29, N 1. P. 47–52.Payan C. // Discrete Math. 1980. Vol. 29, N 1. P. 47–52.Mahadev N. V. R., Peled U. N., Sun F. // J. Graph Theory. 1994. Vol. 18, N 3. P. 281–299.Mahadev N. V. R., Peled U. N., Sun F. // J. Graph Theory. 1994. Vol. 18, N 3. P. 281–299.Mahadev N. V. R., Peled U. N. Threshold graphs and related topics. Amsterdam: Elsevier, 1995.Mahadev N. V. R., Peled U. N. Threshold graphs and related topics. Amsterdam: Elsevier, 1995.De Temple D., Robertson J. M. // J. Aust. Math. Soc., Ser. A. 1989. Vol. 47, N 3. P. 391–398.De Temple D., Robertson J. M. // J. Aust. Math. Soc., Ser. A. 1989. Vol. 47, N 3. P. 391–398.McMorris F. R., Zaslavsky T. // J. Combin. Inform. System Sci. 1982. Vol. 7, N 2. P. 134–138.McMorris F. R., Zaslavsky T. // J. Combin. Inform. System Sci. 1982. Vol. 7, N 2. P. 134–138.Skowrońsk M., Sysło M. // Discrete Appl. Math. 1984. Vol. 7. P. 201–208.Skowrońsk M., Sysło M. // Discrete Appl. Math. 1984. Vol. 7. P. 201–208.Cheston G. A., Jap T. S. // J. Graph Algorithms Appl. 2006. Vol. 10, N 2. P. 159–190.Cheston G. A., Jap T. S. // J. Graph Algorithms Appl. 2006. Vol. 10, N 2. P. 159–190.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 1990.Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 1990.Berge C. Graphs and hypergraphs. New York: American Elsevier Publishing Company, 1976.Berge C. Graphs and hypergraphs. New York: American Elsevier Publishing Company, 1976.Bollobás B., Cockayne E. J. // J. Graph Theory. 1979. Vol. 3, N 3. P. 241–250.Bollobás B., Cockayne E. J. // J. Graph Theory. 1979. Vol. 3, N 3. P. 241–250.Cockayne E. J., Hedetniemi S. T., Miller D. J. // Canad. Math. Bull. 1978. Vol. 21. P. 461–468.Cockayne E. J., Hedetniemi S. T., Miller D. J. // Canad. Math. Bull. 1978. Vol. 21. P. 461–468.Sampathkumar E., Neeralagi P. S. // Indian J. Pure Appl. Math. 1985. Vol. 16. P. 126–132.Sampathkumar E., Neeralagi P. S. // Indian J. Pure Appl. Math. 1985. Vol. 16. P. 126–132.Sampathkumar E., Neeralagi P. S. // J. Combin. Inf. Syst. Sci. 1994. Vol. 19. P. 139–145.Sampathkumar E., Neeralagi P. S. // J. Combin. Inf. Syst. Sci. 1994. Vol. 19. P. 139–145.Cheston G. A., Hare E. O., Hedetniemi S. T., Laskar R. C. // Congr. Numer. 1988. Vol. 67. P. 105–113.Cheston G. A., Hare E. O., Hedetniemi S. T., Laskar R. C. // Congr. Numer. 1988. Vol. 67. P. 105–113.Lundgren J. R., Maybee J. S. // Congr. Numer. 1983. Vol. 40. P. 189–193.Lundgren J. R., Maybee J. S. // Congr. Numer. 1983. Vol. 40. P. 189–193.Ogawa K., Tagusari S., Tsuchiya M. // Discrete Math. 2009. Vol. 309. P. 3659–3663.Ogawa K., Tagusari S., Tsuchiya M. // Discrete Math. 2009. Vol. 309. P. 3659–3663.Cheston G. A., Fricke G. // Discrete Appl. Math. 1994. Vol. 55. P. 241–258.Cheston G. A., Fricke G. // Discrete Appl. Math. 1994. Vol. 55. P. 241–258.Raz R., Safra S. // Proc. of the 29th annual ACM symp. on theory of computing. New York: ACM Press, 1997. P. 475–484.Raz R., Safra S. // Proc. of the 29th annual ACM symp. on theory of computing. New York: ACM Press, 1997. P. 475–484.Paz A., Moran S. // Theor. Comput. Sci. 1981. Vol. 15. P. 251–277.Paz A., Moran S. // Theor. Comput. Sci. 1981. Vol. 15. P. 251–277.Kann V. On the approximability of NP-complete optimization problems: Ph. D. thesis / Royal Institute of Technology. Stockholm, 1992.Kann V. On the approximability of NP-complete optimization problems: Ph. D. thesis / Royal Institute of Technology. Stockholm, 1992.

The authors declare that there are no conflicts of interest present.