ALGORITHMIC PROPERTIES OF CONNECTED NEIGHBOURHOOD SETS IN GRAPHS
Abstract
We introduce and characterize the class of graphs in which every connected dominating set is a (connected) neighbourhood set and a class of graphs whose all connected induced subgraphs have equal minimum neighbourhood set and minimum connected neighbourhood set cardinalities. Assuming P ≠ NP, we also prove that the minimum connected neighbourhood set problem cannot be approximated within a logarithmic factor in polynomial time in their common subclass, the class of simplicial split graphs.
References
1. Sampathkumar, E. The neighbourhood number of a graph / E. Sampathkumar, P. S. Neeralagi // Indian J. Pure Appl. Math. – 1985. – Vol. 16. – P. 126–132.
2. Sampathkumar, E. The connected domination number of a graph / E. Sampathkumar, H. B. Walikar // J. Math. Phys. Sci. – 1979. – Vol. 13. – P. 607–613.
3. Sampathkumar, E. Independent, perfect and connected neighbourhood numbers of a graph / E. Sampathkumar, P. S. Neeralagi // J. Comb. Inf. Syst. Sci. – 1994. – Vol. 19. – P. 139–145.
4. Картынник, Ю. А. Доминантно-треугольные графы и графы верхних границ / Ю. А. Картынник, Ю. Л. Орлович // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 1. – С. 16– 25.
5. Földes, S. Split graphs / S. Földes, P. L. Hammer // Congress. Numer. – 1978. – No. 19. – P. 311–315.
6. Тышкевич, Р. И. Каноническое разложение графа, определяемого степенями его вершин / Р. И. Тышкевич, А. А. Черняк // Изв. АН БССР. Сер. физ.-мат. наук. – 1979. – Т. 5. – С. 14–26.
7. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990.
8. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982.
9. Zverovich, I. E. Perfect connected-dominant graphs / I. E. Zverovich // Discuss. Math. Graph Theory. – 2003. – Vol. 23. – P. 159–162.
Review
Views: 740
Email this article 