A note on a sparse set of hypercube

Abstract

In this paper, we study vertex-induced subgraphs of the hypercube that have the minimum possible number of edges for a given set of vertices, which we refer to as sparse sets. More precisely, for a positive integer $k$, let $n$ be such that $2^{n-1}$ $\leq $ $k$ $<$ $ 2^n$.
A sparse set on $k$ vertices is defined as a vertex-induced subgraph of $Q_n$ with $k$ vertices that attains the minimum number of edges among all such induced subgraphs. We establish several properties of sparse sets. Such as the number of minimum edges on a given set of vertices in $Q_n$. Also, study sparse set when $k$ is of the form $2^{n-1}$, $2^{n-1} -1$, $2^{n-1} -2$, $2^n-2$ and $2^{n} -1$ in hypercube $Q_n$, among other results.