RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2020 Volume 32, Issue 2, Pages 71–84 (Mi dm1554)

Trees with a given number of leaves and the maximal number of maximum independent sets

D. S. Taletskiia, D. S. Malyshevb

a Lobachevski State University of Nizhni Novgorod
b State University – Higher School of Economics, Nizhny Novgorod Branch

Abstract: A complete description of trees with maximal possible number of maximum independent sets among all $n$-vertex trees with exactly $l$ leaves is obtained. For all values of the parameters $n$ and $l$ the extremal tree is unique and is the result of merging the endpoints of $l$ simple paths.

Keywords: independent set, maximum independent set, maximal independent set, extremal tree.

UDC: 519.176+519.172.1

Received: 06.12.2018
Revised: 14.05.2020

DOI: 10.4213/dm1554


 English version:
Discrete Mathematics and Applications, 2021, 31:2, 135–144

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024