On the maximum number of maximum independent sets in connected graphs
Elena Mohr, Dieter Rautenbach
Abstract
Abstract 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.
Topics & Concepts
CombinatoricsMathematicsIndependence numberSplit graphCographChordal graphClique-sumDiscrete mathematicsVertex (graph theory)ConjectureIndependent setDisjoint setsBlock graphGraph1-planar graphAdvanced Graph Theory ResearchGraph theory and applicationsLimits and Structures in Graph Theory