Characterizes connected graphs maximizing independent sets in specified orders, implying unique graph structures.
We characterize the connected graphs of given order and given independence number that maximize the number of maximum independent sets. For , there is a unique such graph that arises from the disjoint union of cliques of orders and , which is the complement of a Turán graph, by selecting a vertex in a largest clique and adding an edge between and a vertex in each of the remaining cliques. Our result confirms a conjecture of Derikvand and Oboudi.
No takes yet. Share an insight, caveat, or question.
Mohr et al. (2020) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: