arXiv Analytics

Sign in

arXiv:1610.06058 [math.CO]AbstractReferencesReviewsResources

Coverings, Matchings and the number of maximal independent sets of graphs

Do Trong Hoang, Tran Nam Trung

Published 2016-10-19Version 1

We determine the maximum number of maximal independent sets of arbitrary graphs in terms of their covering numbers and we completely characterize the extremal graphs. As an application, we give a similar result for K\"onig-Egerv\'ary graphs in terms of their matching numbers.

Comments: 7 pages, 1 figure
Categories: math.CO
Related articles: Most relevant | Search more
arXiv:math/0207100 [math.CO] (Published 2002-07-11, updated 2005-04-30)
Maximal Independent Sets In Graphs With At Most r Cycles
arXiv:2001.02628 [math.CO] (Published 2020-01-07)
Extremal graphs for wheels
arXiv:1809.01901 [math.CO] (Published 2018-09-06)
Extremal graphs for vertex-degree-based invariants with given degree sequences

Links

Toolbox