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


Abstract in English

Let ${[n] choose k}$ and ${[n] choose l}$ $( 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} = ({[n] choose k},{[n] choose l},E)$ such that two vertices $S, epsilon ,{[n] choose k} $ and $T, epsilon ,{[n] choose l} $ 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$.

Download