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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2023},
     volume = {30},
     number = {3},
     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
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
%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/

[1] Pedersen A. S., Vestergaard P. D., “An upper bound on the number of independent sets in a tree”, Ars Comb., 84 (2007), 85–96 | MR | Zbl

[2] Frendrup A., Pedersen A. S., Sapozhenko A. A., Vestergaard P. D., “Merrifield–Simmons index and minimum number of independent sets in short trees”, Ars Comb., 111 (2013), 85–95 | MR | Zbl

[3] A. B. Dainyak, “On the number of independent sets in the trees of a fixed diameter”, J. Appl. Ind. Math., 4:2 (2010), 163–171 | DOI | MR | MR | Zbl

[4] D. S. Taletskii, “Trees of diameter $6$ and $7$ with minimum number of independent sets”, Math. Notes, 109:1–2 (2021), 280–291 | DOI | DOI | MR | Zbl

[5] Atkinson G., Frieze A., “On the $b$-independence number of sparse random graphs”, Comb. Probab. Comput., 13:3 (2004), 295–309 | DOI | MR | Zbl

[6] Abiad A., Cioabă S. M., Tait M., “Spectral bounds for the $k$-independence number of a graph”, Linear Algebra Appl., 510 (2016), 160–170 | DOI | MR | Zbl

[7] Bouchou A., Blidia M., “On the $k$-independence number in graphs”, Australas. J. Comb., 59:2 (2014), 311–322 | MR | Zbl

[8] O S., Shi Y., Taoqiu Z., “Sharp upper bounds on the $k$-independence number in graphs with given minimum and maximum degree”, Graphs Comb., 37 (2020), 393–408 | MR

[9] Li Z., Wu B., “The $k$-independence number of $t$-connected graphs”, Appl. Math. Comput., 409 (2021), 126412, 4 pp. | MR | Zbl

[10] Jou M. J., Lin J. J., “Characterization of the distance-$k$ independent dominating sets of the $n$-path”, Int. J. Contemp. Math. Sci., 13:6 (2018), 231–238 | DOI