Trees with a given number of leaves and the maximal number of maximum independent sets (Q2031165)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Trees with a given number of leaves and the maximal number of maximum independent sets |
scientific article |
Statements
Trees with a given number of leaves and the maximal number of maximum independent sets (English)
0 references
8 June 2021
0 references
In this English translation from the original Russian, the authors give a complete description of the \(n\)-vertex trees with precisely \(\ell\) leaves having the maximal number of maximum independent sets. For a fixed \(n\) and \(\ell\), the extremal tree is unique. Further, it is the result of ``merging the endpoints of \(\ell\) simple paths''. The proof of this result comes from a careful and well-written study of the structure of such trees.
0 references
independent set
0 references
maximum independent set
0 references
maximal independent set
0 references
extremal tree
0 references