Domination, Packing and Excluded Minors

Abstract

Let $\gamma(G)$ be the domination number of a graph $G$, and let $\alpha_k(G)$ be the maximum number of vertices in $G$, no two of which are at distance $\le k$ in $G$. It is easy to see that $\gamma(G)\ge \alpha_2(G)$. In this note it is proved that $\gamma(G)$ is bounded from above by a linear function in $\alpha_2(G)$ if $G$ has no large complete bipartite graph minors. Extensions to other parameters $\alpha_k(G)$ are also derived.