Том 27, номер 2, 2020 г., Стр. 65-89

УДК 519.17
Ловеров Я. А., Орлович Ю. Л.
NP-полнота задачи о независимом доминирующем множестве в классе кубических планарных
двудольных графов

Аннотация:
Известно, что как в классе кубических планарных графов, так и в классе кубических двудольных графов задача о независимом доминирующем множестве NP-полна. Вопрос о вычислительной сложности данной задачи в пересечении вышеупомянутых классов является открытым. В настоящей работе доказывается, что в классе кубических планарных двудольных графов задача о независимом доминирующем множестве также NP-полна.
Табл. 1, ил. 7, библиогр. 19.

Ключевые слова: независимое доминирующее множество, кубический граф, планарный граф, двудольный граф, NP-полнота.

DOI: 10.33048/daio.2020.27.657

Ловеров Ярослав Анатольевич ¹
Орлович Юрий Леонидович ¹
1. Белорусский гос. университет,
пр. Независимости, 4, 220030 Минск, Беларусь
е-mail: loverov@bsu.by, orlovich@bsu.by

Статья поступила 11 апреля 2019 г.
После доработки — 20 декабря 2019 г.
Принята к публикации 13 января 2020 г.

Литература

[1] Ore O. Theory of graphs. Providence, RI: Amer. Math. Soc., 1962. 284 p.

[2] Cockayne E. J., Hedetniemi S. T. Independence graphs // Congr. Numerantium. 1974. Vol. X. P. 471–491.

[3] Sampathkumar E., Walikar H. B. The connected domination number of a graph // J. Math. Phys. Sci. 1979. Vol. 13. P. 607–613.

[4] Cockayne E. J., Dawes R. M., Hedetniemi S. T. Total domination in graphs // Networks. 1980. Vol. 10. P. 211–219.

[5] Bollobás B., Cockayne E. J. Graph-theoretic parameters concerning domination, independence, and irredundance // J. Graph Theory. 1979. Vol. 3, No. 3. P. 241–249.

[6] Cockayne E. J., Hartnell B. L., Hedetniemi S. T., Laskar R. Perfect domination in graphs // J. Comb. Inf. Syst. Sci. 1993. Vol. 18. P. 136–148.

[7] Sampathkumar E., Neeralagi P. S. The neighbourhood number of a graph // Indian J. Pure Appl. Math. 1985. Vol. 16. P. 126–132.

[8] Sampathkumar E., Neeralagi P. S. Independent, perfect and connected neighbourhood numbers of a graph // J. Comb. Inf. Syst. Sci. 1994. Vol. 19. P. 139–145.

[9] Haynes T. W., Hedetniemi S. T., Slater P. J. Domination in graphs: advanced topics. New York: Marcel Dekker, 1998. 520 p.

[10] Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of domination in graphs. New York: Marcel Dekker, 1998. 457 p.

[11] Du D.-Z., Wan P.-J. Connected dominating set: theory and applications. New York: Springer, 2013. 216 p.

[12] Goddard W., Henning M. A. Independent domination in graphs: a survey and recent results // Discrete Math. 2013. Vol. 313. P. 839–854.

[13] Henning M., Yeo A. Total domination in graphs. New York: Springer, 2013. 192 p.

[14] Liu C.-H., Poon S.-H., Lin J.-Y. Independent dominating set problem revisited // Theor. Comput. Sci. 2015. Vol. 562. P. 1–22.

[15] Berge C. Graphs and hypergraphs. Amsterdam: North-Holland Publ. Co., 1973. 528 p.

[16] Topp J. Domination, independence and irredundance in graphs // Diss. Math. 1995. Vol. 342. 99 p.

[17] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[18] Manlove D. F. On the algorithmic complexity of twelve covering and independence parameters of graphs // Discrete Appl. Math. 1999. Vol. 91. P. 155–175.

[19] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.