Том 27, номер 1, 2020 г., Стр. 61-87

УДК 519.172.1
Курносов А. Д.
Множество всех возможных значений числа доминирования в деревьях с заданной степенной последовательностью

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

Ключевые слова: степенная последовательность, дерево, число доминирования, обратная задача, реализация, реализующее дерево.

DOI: 10.33048/daio.2020.27.656

Курносов Артем Дмитриевич ¹
1. Московский физико-технический институт,
Институтский пер., 9, 141700 Долгопрудный, Россия
е-mail: kurnosov@phystech.edu

Статья поступила 6 апреля 2019 г.
После доработки — 21 августа 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

[1] Diestel R. Graph theory. Heidelberg: Springer, 2016. (Grad. Texts Math.; Vol. 173).

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

[3] Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of domination in graphs. New York: Marcel Dekker, 1998 (Monogr. Textb. Pure Appl. Math.).

[4] Дайняк А. Б., Курносов А. Д. Об одной экстремальной обратной задаче теории графов // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 1. С. 19–31.

[5] Havel V. A remark on the existence of finite graphs // Cas. Pestování Mat. 1955. Vol. 80. P. 477–480. [Czech.]

[6] Hakimi S. On the realizability of a set of integers as degrees of the vertices of a graph // SIAM J. Appl. Math. 1962. Vol. 10. P. 496–506.

[7] Favaron O. A bound on the independent domination number of a tree // Vishwa Int. J. Graph Theory. 1992. Vol. 1, No. 1. P. 19–27.

[8] Gentner M., Henning M., Rautenbach D. Largest domination number and smallest independence number of forests with given degree sequence // Discrete Appl. Math. 2016. Vol. 206. P. 181–187.

[9] Gentner M., Henning M., Rautenbach D. Smallest domination number and largest independence number of graphs and forests with given degree sequence // J. Graph Theory. 2018. Vol. 88, No. 1. P. 131–145.

[10] Lemanska M. Lower bound on the domination number of a tree // Discus. Math. Graph Theory. 2004. Vol. 24. P. 165–169.

[11] Slater P. J. Locating dominating sets and locating-dominating sets // Graph theory, combinatorics and applications. Proc. 7th Quad. Int. Conf. Theory Appl. Graphs (Kalamazoo, USA, June 1–5, 1992). Vol. 2. New York: Wiley, 1995. P. 1073–1079.

[12] Desormeaux W. J, Haynes T. W., Henning M. A. Improved bounds on the domination number of a tree // Discrete Appl. Math. 2014. Vol. 177. P. 88–94.