The domination number of the graph defined by two levels of the $n$-cube, II

Abstract

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}$ was exactly determined by Badakhshian, Katona and Tuza. A conjecture was also stated there on the asymptotic value ($n$ tending to infinity) of the domination number of $G_{k,2}$. Here we prove the conjecture, determining the asymptotic value of the domination number $\gamma (G_{k,2})=\frac{k+3}{2(k-1)(k+1)}{n}^2+o(n^2)$.

Minor revisions

References in corpus (1)

• Some results on domination number of the graph defined by two levels of the n-cube

Cited by in corpus (1)

• On the domination number of $t$-constrained de Bruijn graphs