Geodesic
The set of all values of the domination number in~trees with~a~given degree sequence
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 61-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2020_27_1_a3,
     author = {A. D. Kurnosov},
     title = {The set of all values of the domination number in~trees with~a~given degree sequence},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {61--87},
     publisher = {mathdoc},
     volume = {27},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_1_a3/}
}
TY  - JOUR
AU  - A. D. Kurnosov
TI  - The set of all values of the domination number in~trees with~a~given degree sequence
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 61
EP  - 87
VL  - 27
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_1_a3/
LA  - ru
ID  - DA_2020_27_1_a3
ER  - 
%0 Journal Article
%A A. D. Kurnosov
%T The set of all values of the domination number in~trees with~a~given degree sequence
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 61-87
%V 27
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_1_a3/
%G ru
%F DA_2020_27_1_a3
A. D. Kurnosov. The set of all values of the domination number in~trees with~a~given degree sequence. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 1, pp. 61-87. http://geodesic.mathdoc.fr/item/DA_2020_27_1_a3/

[1] R. Diestel, Graph theory, Grad. Texts Math., 173, Springer, Heidelberg, 2016 | MR

[2] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, v. I, Wissenschaftsverlag, Mannheim, 1994 | MR | MR

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

[4] A. B. Dainyak, A. D. Kurnosov, “On an extremal inverse problem in graph theory”, J. Appl. Ind. Math., 9:1 (2015), 157–164 | DOI | MR | Zbl

[5] V. Havel, “A remark on the existence of finite graphs”, Čas. Pěstování Mat., 80 (1955), 477–480 (Czech.) | MR | Zbl

[6] “Hakimi S”, SIAM J. Appl. Math., 10 (1962), 496–506 | DOI | MR

[7] O. Favaron, “A bound on the independent domination number of a tree”, Vishwa Int. J. Graph Theory, 1:1 (1992), 19–27 | MR

[8] M. Gentner, M. Henning, D. Rautenbach, “Largest domination number and smallest independence number of forests with given degree sequence”, Discrete Appl. Math., 206 (2016), 181–187 | DOI | MR | Zbl

[9] M. Gentner, M. Henning, D. Rautenbach, “Smallest domination number and largest independence number of graphs and forests with given degree sequence”, J. Graph Theory, 88:1 (2018), 131–145 | DOI | MR | Zbl

[10] M. Lemanska, “Lower Bound on the Domination Number of a Tree”, Discuss. Math., Graph Theory, 24 (2004), 165–169 | DOI | MR | Zbl

[11] P. J. Slater, “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), v. 2, Wiley, New York, 1995, 1073–1079 | MR | Zbl

[12] Desormeaux W. J, T. W. Haynes, M. A. Henning, “Improved bounds on the domination number of a tree”, Discrete Appl. Math., 177 (2014), 88–94 | DOI | MR | Zbl