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