Introduction to Graph Theory · Problem 2.20

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · heinrich-tittmann-formula-dominating-sets

Problem

Let

G = (V, E)

be a simple graph with at least one vertex. Let

n = |V|

. A detached pair means a pair

(A, B)

of two disjoint subsets

A

and

B

V

such that there exists no edge

ab \in E

with

a \in A

and

b \in B

. Prove the following generalization of the Heinrich--Tittmann formula:

\sum_{\substack{S \text{ is a dominating} \\ \text{set of } G}} x^{|S|} = (1+x)^n - 1 + \sum_{\substack{(A,B) \text{ is a detached pair;} \\ A \neq \varnothing;\, B \neq \varnothing}} (-1)^{|A|} x^{|B|}.

(Here, both sides are polynomials in a single indeterminate

x

with coefficients in

\mathbb{Z}

.) [Hint: This is a generalization of the Heinrich--Tittmann formula for the number of dominating sets. (The latter formula can be obtained fairly easily by substituting

x = 1

into the above and subsequently cancelling the addends with

|A| \not\equiv |B| \bmod 2

against each other.) You are free to copy arguments from [17s] and change whatever needs to be changed. (Some lemmas can even be used without any changes -- they can then be cited without proof.)]

Browse the problem library