On the number of maximum independent sets of graphs

Document Type : Research Paper


1 Islamic Azad University of Marvdasht

2 University of Isfahan


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


Main Subjects

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
  • Receive Date: 06 December 2013
  • Revise Date: 01 January 2014
  • Accept Date: 03 January 2014
  • Published Online: 01 March 2014