We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the maximum number of maximum independent sets in connected graphs.
- Authors
Mohr, Elena; Rautenbach, Dieter
- Abstract
We characterize the connected graphs of given order n and given independence number α that maximize the number of maximum independent sets. For 3≤α≤n∕2, there is a unique such graph that arises from the disjoint union of α cliques of orders ⌈nα⌉ and ⌊nα⌋, which is the complement of a Turán graph, by selecting a vertex x in a largest clique and adding an edge between x and a vertex in each of the remaining α−1 cliques. Our result confirms a conjecture of Derikvand and Oboudi.
- Subjects
DA Nang (Vietnam); INDEPENDENT sets; GRAPH connectivity; INDEPENDENCE (Mathematics)
- Publication
Journal of Graph Theory, 2021, Vol 96, Issue 4, p510
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22629