pith. sign in

arxiv: 1804.00158 · v2 · pith:53IG74YUnew · submitted 2018-03-31 · 🧮 math.CO

On the maximum number of minimum dominating sets in forests

classification 🧮 math.CO
keywords gammanumbersetsdominatingminimumdominationeveryforests
0
0 comments X
read the original abstract

Fricke, Hedetniemi, Hedetniemi, and Hutson asked whether every tree with domination number $\gamma$ has at most $2^\gamma$ minimum dominating sets. Bien gave a counterexample, which allows to construct forests with domination number $\gamma$ and $2.0598^\gamma$ minimum dominating sets. We show that every forest with domination number $\gamma$ has at most $2.4606^\gamma$ minimum dominating sets, and that every tree with independence number $\alpha$ has at most $2^{\alpha-1}+1$ maximum independent sets.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.