G.O.H. Katona: The domination number of the graph defined by two levels of the n-cube

Consider all $k$-element subsets and $\ell$-element subsets $(k>\ell )$ of an $n$-element set as vertices of a bipartite graph.

Two vertices are adjacent if the corresponding $\ell$-element set is a subset of the corresponding $k$-element set.

Let $G_{k,\ell}$ denote this graph

The domination number of $G_{k,1}$ will exactly be determined. We also give lower and upper estimates on the domination number

$G_{k,2}$ and pose a conjecture of asymptotic nature.