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

Diskretn. Anal. Issled. Oper., 2023 Volume 30, Issue 3, Pages 111–131 (Mi da1330)

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.

UDC: 519.17

Received: 20.10.2022
Revised: 02.05.2023
Accepted: 11.05.2023

DOI: 10.33048/daio.2023.30.755



© Steklov Math. Inst. of RAS, 2025