Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 131-147
Volume 27, No 1, 2020, P. 61-87
UDC 519.172.1
A. D. Kurnosov
The set of all values of the domination number in trees with a given degree sequence
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.
DOI: 10.33048/daio.2020.27.656
Artem D. Kurnosov 1
1. Moscow Institute of Physics and Technology,
9 Institutskii Lane, 9, 141700 Dolgoprudnyi, Russia
e-mail: kurnosov@phystech.edu
Received April 6, 2019
Revised August 21, 2019
Accepted August 28, 2019
References
[1] R. Diestel, Graph Theory (Springer, Heidelberg, 2016).[2] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990; B. I. Wissenschaftsverlag, Mannheim, 1994).
[3] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[4] A. B. Dainyak and A. D. Kurnosov, On an extremal inverse problem in graph theory, Diskretn. Anal. Issled. Oper. 22 (1), 19–30 (2015) [J. Appl. Ind. Math. 9 (2), 157–164 (2015)].
[5] V. Havel, A remark on the existence of finite graphs, Cas. Pestování Mat. 80 (4), 477–480 (1955).
[6] S. Hakimi, On the realizability of a set of integers as degrees of the vertices of a graph, SIAM J. Appl. Math. 10, 496–506 (1962).
[7] O. Favaron, A bound on the independent domination number of a tree, Vishwa Int. J. Graph Theory 1 (1), 19–27 (1992).
[8] M. Gentner, M. Henning, and D. Rautenbach, Largest domination number and smallest independence number of forests with given degree sequence, Discrete Appl. Math. 206, 181–187 (2016).
[9] M. Gentner, M. Henning, and D. Rautenbach, Smallest domination number and largest independence number of graphs and forests with given degree sequence, J. Graph Theory 88 (1), 131–145 (2018).
[10] M. Lemanska, Lower Bound on the Domination Number of a Tree, Discuss. Math., Graph Theory 24, 165–169 (2004).
[11] P. J. Slater, Locating dominating sets and locating-dominating sets, in Graph Theory, Combinatorics and Applications (Proc. 7th Quadrennial Int. Conf. Theory and Applications of Graphs, Kalamazoo, USA, June 1–5, 1992), Vol. 2 (Wiley, New York, 1995), pp. 1073–1079.
[12] W. J. Desormeaux, T. W. Haynes, and M. A. Henning, Improved bounds on the domination number of a tree, Discrete Appl. Math. 177, 88–94 (2014).
