|
The set of all values of the domination number in trees with a given degree sequence
A. D. Kurnosov Moscow Institute of Physics and Technology, 9 Institutskii Lane, 9, 141700 Dolgoprudnyi, Russia
Abstract:
We find the set of all values of the domination number for a class of trees with some given vertex degrees that forms a segment of naturals. We prove that each intermediate value of the segment can be obtained by gradually changing the tree that minimizes the domination number and with the use of two special operations, so that the last tree maximizes the domination number. Illustr. 1, bibliogr. 12.
Keywords:
degree sequence, tree, domination number, inverse problem, realization, realization tree.
Received: 06.04.2019 Revised: 21.08.2019 Accepted: 28.08.2019
Citation:
A. D. Kurnosov, “The set of all values of the domination number in trees with a given degree sequence”, Diskretn. Anal. Issled. Oper., 27:1 (2020), 61–87; J. Appl. Industr. Math., 14:1 (2020), 131–147
Linking options:
https://www.mathnet.ru/eng/da944 https://www.mathnet.ru/eng/da/v27/i1/p61
|
Statistics & downloads: |
Abstract page: | 264 | Full-text PDF : | 105 | References: | 24 | First page: | 6 |
|