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$.

Keywords

• Independent set
• independence number
• Maximum independent set