Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

ДОМИНАНТНО-ТРЕУГОЛЬНЫЕ ГРАФЫ И ГРАФЫ ВЕРХНИХ ГРАНИЦ

Полный текст:

Аннотация

В работе вводится и изучается собственный подкласс треугольных графов, а именно доминантно-треугольные графы. Граф 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.


Просмотров: 293


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)