z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom