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

Abstract

Let $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ and $\left(\genfrac{}{}{0ex}{}{[n]}{l}\right)$ $(k>l)$ where $[n]=\{1,2,3,...,n\}$ denote the family of all $k$-element subsets and $l$-element subsets of $[n]$ respectively. Define a bipartite graph $G_{k,l}=((\genfrac{}{}{0ex}{}{[n]}{k}),(\genfrac{}{}{0ex}{}{[n]}{l}),E)$ such that two vertices $S\epsilon \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ and $T\epsilon \left(\genfrac{}{}{0ex}{}{[n]}{l}\right)$ are adjacent if and only if $T\subset S$. In this paper, we give an upper bound for the domination number of graph $G_{k,2}$ for $k>\lceil \frac{n}{2}\rceil$ and exact value for $k=n-1$.

Cited by in corpus (1)

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