Transactions on Combinatorics (Mar 2014)
On the number of maximum independent sets of graphs
Abstract
Let $G$ be a simple graph. An independent set is a set of pairwise non-adjacent vertices. The number of vertices in a maximum independent set of $G$ is denoted by $alpha(G)$. In this paper, we characterize graphs $G$ with $n$ vertices and with maximum number of maximum independent sets provided that $alpha(G)leq 2$ or $alpha(G)geq n-3$.