Premium
On the maximum number of maximum independent sets in connected graphs
Author(s) -
Mohr Elena,
Rautenbach Dieter
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22629
Subject(s) - combinatorics , mathematics , independence number , split graph , cograph , chordal graph , clique sum , discrete mathematics , vertex (graph theory) , conjecture , independent set , disjoint sets , block graph , graph , 1 planar graph
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.