On a conjecture of Badakhshian, Katona and Tuza

Yeshwant Pandit, S. L. Sravanthi, Suresh Dara, S. M. Hegde

Published 2019-09-30Version 1

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 disprove the conjecture of Badakhshian, Katona and Tuza for $k= \lceil \frac{n}{2} \rceil +1 $ and $k=n-1$ for $n\geq 10$ and $n>2$ respectively. Also, we give an upper bound for the domination number of $G_{k,2}$ for $k > \lceil \frac{n}{2} \rceil$.