On the maximum number of minimum dominating sets in forests

2018/03/31 by José D. Alvarado, Simone Dantas, Alvarado, J. D. +5
Computer Science · #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1804.00158

Abstract

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

Related

• Largest Domination Number and Smallest Independence Number of Forests with given Degree Sequence
• Domination game on forests
• The Domination Game: Proving the 3/5 Conjecture on Isolate-Free Forests
• Bounding the number of (σ,ρ)-dominating sets in trees, forests and graphs of bounded pathwidth
• The ratio of domination and independent domination numbers on trees