Trees with the Second and Third Largest Number of Maximum Independent Sets

Abstract

An independent set in a graph $G$ is a subset $I$ of the vertices such that no two vertices in $I$ are adjacent. We say that $I$ is a maximum independent set in $G$ if no other independent set is larger than $I$. In this paper, we study the problem of determining the second and third largest number of maximum independent sets among all trees and forests. Extremal graphs achieving these values are also given.