Geodesic
Trees of Diameter $6$ and $7$ with Minimum Number of Independent Sets
Matematičeskie zametki, Tome 109 (2021) no. 2, pp. 276-289
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the problem of describing $n$-vertex trees of diameter $d$ containing as few independent sets as possible. This problem is solved for $d=6$ and $n>160$, as well as for $d=7$ and $n>400$.
Keywords: independent set, tree, diameter. 
@article{MZM_2021_109_2_a10,
     author = {D. S. Taletskii},
     title = {Trees of {Diameter} $6$ and $7$ with {Minimum} {Number} of {Independent} {Sets}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {276--289},
     year = {2021},
     volume = {109},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2021_109_2_a10/}
}
TY  - JOUR
AU  - D. S. Taletskii
TI  - Trees of Diameter $6$ and $7$ with Minimum Number of Independent Sets
JO  - Matematičeskie zametki
PY  - 2021
SP  - 276
EP  - 289
VL  - 109
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MZM_2021_109_2_a10/
LA  - ru
ID  - MZM_2021_109_2_a10
ER  - 
%0 Journal Article
%A D. S. Taletskii
%T Trees of Diameter $6$ and $7$ with Minimum Number of Independent Sets
%J Matematičeskie zametki
%D 2021
%P 276-289
%V 109
%N 2
%U http://geodesic.mathdoc.fr/item/MZM_2021_109_2_a10/
%G ru
%F MZM_2021_109_2_a10
D. S. Taletskii. Trees of Diameter $6$ and $7$ with Minimum Number of Independent Sets. Matematičeskie zametki, Tome 109 (2021) no. 2, pp. 276-289. http://geodesic.mathdoc.fr/item/MZM_2021_109_2_a10/

[1] H. Prodinger, R. F. Tichy, “Fibonacci numbers of graphs”, Fibonacci Quart., 19:1 (1982), 16–21 | MR

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

[3] A. B. Dainiak, Sharp Bounds for the Number of Maximal Independent Sets in Trees of Fixed Diameter, 2008, arXiv: 0812.4948

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

[5] A. B. Dainyak, “O chisle nezavisimykh mnozhestv v derevyakh fiksirovannogo diametra”, Diskretn. analiz i issled. oper., 16:2 (2009), 61–73 | MR | Zbl