A note on the number of dominating sets of a graph

Abstract

In a recent article by Bród and Skupień, sharp upper and lower bounds for the number of dominating sets in a tree were determined. In the present paper we show that the lower bound even holds for graphs without isolated vertices and characterise the cases of equality. Further results on this graph parameter are a Turán-type theorem for the number of dominating sets of a graph with given domination number, and a Nordhaus-Gaddum inequality.