|
On trees with given diameter and extremal number of distance-$k$ independent sets
D. S. Taletskiiab a National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
b Lobachevsky Nizhny Novgorod State University, 23 Gagarin Avenue, 603950 Nizhny Novgorod, Russia
Abstract:
The set of vertices of a graph is called distance-$k$ independent if the distance between any two of its vertices is greater than some integer $k \geq 1.$ In this paper we describe $n$-vertex trees with a given diameter $d$ which have maximum and minimum possible number of distance-$k$ independent sets among all such trees. The maximum problem is solved for the case $1 < k < d \leq 5.$ The minimum problem is significantly more simple and is solved for all $1 < k < d < n.$ Illustr. 4, bibliogr. 10.
Keywords:
tree, independent set, distance-$k$ independent set, diameter.
Received: 20.10.2022 Revised: 02.05.2023 Accepted: 11.05.2023
Citation:
D. S. Taletskii, “On trees with given diameter and extremal number of distance-$k$ independent sets”, Diskretn. Anal. Issled. Oper., 30:3 (2023), 111–131
Linking options:
https://www.mathnet.ru/eng/da1330 https://www.mathnet.ru/eng/da/v30/i3/p111
|
Statistics & downloads: |
Abstract page: | 39 | Full-text PDF : | 6 | References: | 9 | First page: | 3 |
|