Binary trees with extremal number of maximal independent sets
A binary tree (more precisely, an unrooted binary tree) is a tree in which all internal vertices (i.e., non-leaves) are exactly of degree 3. We give an upper bound and a lower bound for the number of maximal independent sets in binary trees together with a characterization of the extremal binary trees. The binary trees with second largest number of maximal independent sets are also characterized.
Institutions
- Uppsala University (SE)
- Stellenbosch University (ZA)
- Kaduna Polytechnic (NG)
- Graz University of Technology (AT)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2025-12-02
- DOI
- https://doi.org/10.1016/j.disc.2025.114911
- Primary Topic
- Graph theory and applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00