Grinberg-Introduction-Graph-Theory · Problem 2.18

Simple graphs

Mathematics — Graph Theory · dominating-sets-kneser-graphs

Problem

Let

n

and

k

be positive integers such that

n \geq k(k+1)

and

k > 1

. Recall (from Subsection 2.6.3) the Kneser graph

KG_{n,k}

, whose vertices are the

k

-element subsets of

\{1, 2, \ldots, n\}

, and whose edges are the unordered pairs

\{A, B\}

of such subsets with

A \cap B = \varnothing

. Prove that the minimum size of a dominating set of

KG_{n,k}

k+1