Geodesic
On trees with given diameter and extremal number of distance-$k$ independent sets
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 111-131

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

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. 
@article{DA_2023_30_3_a5,
     author = {D. S. Taletskii},
     title = {On trees with given diameter and extremal number of distance-$k$ independent sets},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {111--131},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_3_a5/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - On trees with given diameter and extremal number of distance-$k$ independent sets
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 111
EP  - 131
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_3_a5/
LA  - ru
ID  - DA_2023_30_3_a5
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T On trees with given diameter and extremal number of distance-$k$ independent sets
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 111-131
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_3_a5/
%G ru
%F DA_2023_30_3_a5
D. S. Taletskii. On trees with given diameter and extremal number of distance-$k$ independent sets. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 111-131. http://geodesic.mathdoc.fr/item/DA_2023_30_3_a5/