Introduction to Graph Theory · Problem 2.19

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · dominating-sets-distance-bipartition

Problem

Let

G = (V, E)

be a connected simple graph with at least two vertices. The distance

d(v, w)

between two vertices

v

and

w

G

is defined to be the smallest length of a path from

v

w

. (In particular,

d(v,v) = 0

for each

v \in V

.) Fix a vertex

v \in V

. Define two subsets

A = \{w \in V \mid d(v,w) \text{ is even}\} \quad \text{and} \quad B = \{w \in V \mid d(v,w) \text{ is odd}\}

V

. (a) Prove that

A

is dominating. (b) Prove that

B

is dominating. (c) Prove that there exists a dominating set of

G

that has size

\leq |V|/2

. (d) Prove that the claim of part (c) holds even if we don't assume that

G

is connected, as long as we assume that each vertex of

G

has at least one neighbor. (In other words, prove Proposition 2.13.4 (a).)