  In this paper we introduce and study a new graph invariant derived from the
degree sequence of a graph $G$, called the sub-$k$-domination number and
denoted $sub_k(G)$. We show that $sub_k(G)$ is a computationally efficient
sharp lower bound on the $k$-domination number of $G$, and improves on several
known lower bounds. We also characterize the sub-$k$-domination numbers of
several families of graphs, provide structural results on sub-$k$-domination,
and explore properties of graphs which are $sub_k(G)$-critical with respect to
addition and deletion of vertices and edges.
