Transactions on Combinatorics (Mar 2014)

On the number of maximum independent sets of graphs

  • Tajedin Derikvand,
  • Mohammad Reza Oboudi

Journal volume & issue
Vol. 3, no. 1
pp. 29 – 36


Read online

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