Introduction to Graph Theory · Problem 2.21

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · k-path-dominating-sets

Problem

Let

k

be a positive integer. Let

G = (V, E)

be a simple graph. A subset

U

V

will be called

k

-path-dominating if for every

v \in V

, there exists a path of length

\leq k

from

v

to some element of

U

. Prove that the number of all

k

-path-dominating subsets of

V

is odd. [Hint: This is not as substantial a generalization as it may look. The shortest proof is very short.] [Solution: This is Exercise 6 on homework set \#1 from my Spring 2017 course; see the course page for solutions.]

Browse the problem library