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$.
J. Alexander, J. Cutler and T. Mink (2012). Independent sets in graphs with given minimum degree. Electron. J. Combin., Paper 37. 19 (3), 11 N. Alon (1991). Independent sets in regular graphs and sum-free subsets of finite groups. Israel J. Math.. 73, 247-256 D. Cvetkovic and M. Petric (1984). A table of connected graphs on six vertices. Discrete Math.. 50, 37-49 J. Eckhoff (2004). A new Turan-type theorem for cliques in graphs. Discrete Math.. 282, 113-122 B. Hedman (1985). The maximum number of cliques in dense graphs. Discrete Math.. 54, 161-166 G. Hopkins and W. Staton (1985). Graphs with unique maximum independent sets. Discrete Math.. 57, 245-251 M. J. Jou and G. J. Chang (2000). The number of maximum independent sets in graphs. Taiwanese J. Math.. 4, 685-695 M. J. Jou and G. J. Chang (1998). Survey on counting maximal independent sets. Proceedings of the Second Asian Mathematical Conference 1995 (Nakhon Ratchasima), World Sci. Publ., River Edge, N. J.. , 265-275 J. W. Moon and L. Moser (1965). On cliques in graphs. Israel J. Math.. 3, 23-28 S. Roman (1976). The maximum number of q-cliques in a graph with no $p$-clique. Discrete Math.. 14, 365-371 P. Turan (1941). Eine Extremalaufgabe aus der Graphentheorie. (Hungarian) Mat. Fiz. Lapok. 48, 436-452 D. Wood (2007). On the maximum number of cliques in a graph. Graphs Combin.. 23, 337-352 Y. Zhao (2010). The number of independent sets in a regular graph. Combin. Probab. Comput.. 19, 315-320 J. Zito (1991). The structure and maximum number of maximum independent sets in trees. J. Graph Theory. 15, 207-221
Derikvand, T., & Oboudi, M. R. (2014). On the number of maximum independent sets of graphs. Transactions on Combinatorics, 3(1), 29-36. doi: 10.22108/toc.2014.4060
MLA
Tajedin Derikvand; Mohammad Reza Oboudi. "On the number of maximum independent sets of graphs". Transactions on Combinatorics, 3, 1, 2014, 29-36. doi: 10.22108/toc.2014.4060
HARVARD
Derikvand, T., Oboudi, M. R. (2014). 'On the number of maximum independent sets of graphs', Transactions on Combinatorics, 3(1), pp. 29-36. doi: 10.22108/toc.2014.4060
VANCOUVER
Derikvand, T., Oboudi, M. R. On the number of maximum independent sets of graphs. Transactions on Combinatorics, 2014; 3(1): 29-36. doi: 10.22108/toc.2014.4060
)
