arXiv:1111.4442 Abstract | arXiv Analytics

arXiv:1111.4442 [math.CO]Abstract References Reviews Resources

Inverse problems for the number of maximal independent sets

Published 2011-11-18Version 1

We study the following inverse graph-theoretic problem: how many vertices should a graph have given that it has a specified value of some parameter. We obtain asymptotic for the minimal number of vertices of the graph with the given number $n$ of maximal independent sets for a class of natural numbers that can be represented as concatenation of periodic binary words.

Comments: 1 figure, 8 pages

Categories: math.CO, cs.DM

Subjects: 05C35

Keywords: maximal independent sets, inverse problems, inverse graph-theoretic problem, periodic binary words, natural numbers

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

Chee Ying Goh, Khee Meng Koh, Bruce E. Sagan, V. Vatter

arXiv:0812.4948 [math.CO] (Published 2008-12-29)

Sharp bounds for the number of maximal independent sets in trees of fixed diameter

Alexander Dainiak

arXiv:1610.03972 [math.CO] (Published 2016-10-13)