Toward a Nordhaus-Gaddum inequality for the number of dominating sets

Abstract: A dominating set in a graph

G

is a set

S

of vertices such that every vertex of

G

is either in

S

or is adjacent to a vertex in

S

. Nordhaus-Gaddum inequailties relate a graph

G

to its complement

. In this spirit Wagner proved that any graph

G

on

n

vertices satisfies

where

p a r t i a l (G)

is the number of dominating sets in a graph

G

. In the same paper he comments that an upper bound for

among all graphs on

n

vertices seems to be much more difficult. Here we prove an upper bound on

and prove that any graph maximizing this sum has minimum degree at least

l f l o o r n / 2 f l o o r - 2

and maximum degree at most

l f l o o r n / 2 f l o o r + 1

. We conjecture that the complete balanced bipartite graph maximizes

and have verified this computationally for all graphs on at most

10

vertices.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Toward a Nordhaus-Gaddum inequality for the number of dominating sets