On relation between two classes of extremal trees with prescribed degree sequence

S. A. Krupoderova, A. D. Kurnosov

Moscow Institute of Physics and Technology (National Research University), 9 Institutskii Lane, 141700 Dolgoprudnyi, Russia

Abstract: A non-pendant vertex of a graph is called a support vertex if it is adjacent to a leaf. This paper examines the relationship between two classes of extremal trees with the same vertex degree sequence: the class of trees minimizing the number of support vertices and the class of trees minimizing the domination number. Two values defined in terms of a degree sequence play a significant role here: the Slater number, proposed by Slater as a lower bound for the domination number, and the lower bound for the number of support vertices of a tree, proposed by Kurnosov. This paper completely solves the problem of comparing the classes in the case where the maximum of the two values is the latter. Illustr. 2, bibliogr. 14.

Keywords: degree sequence, tree, dominating set, domination number, leaf, pendant vertex, support vertex.

UDC: 519.172.1

Received: 29.01.2025
Revised: 15.03.2025
Accepted: 22.03.2025

DOI: 10.33048/daio.2025.32.826