RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2020 Volume 27, Issue 1, Pages 61–87 (Mi da944)

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.

UDC: 519.172.1

Received: 06.04.2019
Revised: 21.08.2019
Accepted: 28.08.2019

DOI: 10.33048/daio.2020.27.656


 English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 131–147

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024