Distance Domination Critical Graphs

Abstract

For $k\ge 1$ an integer, a set $D$ of vertices of a graph $G=(V,E)$ is a $k$-dominating set of $G$ if every vertex in $V–D$ is within distance $k$ from some vertex of $D$. The $k$-domination number ${\gamma }_k(G)$ of $G$ is the minimum cardinality among all $k$-dominating sets of $G$. For $\ell \ge 2$ an integer, the graph $G$ is $({\gamma }_k,\ell )$-critical if ${\gamma }_k(G)=\ell$ and ${\gamma }_k(G–v)=\ell –1$ for all vertices $v$ of $G$. If $G$ is $({\gamma }_k,\ell )$-critical for some $\ell$, then $G$ is also called a ${\gamma }_k$-critical graph. For a vertex $v$ of $G$, let $N_k(v)=\{u\in V–\{v\}|d(u,v)\le k\}$ and let ${\delta }_k(G)=min\{|N_k(v)|:v\in V\}$ and let ${\mathrm{\Delta }}_k(G)=max\{|N_k(v)|:v\in V\}$. It is shown that if $G$ is a nontrivial connected ${\gamma }_k$-critical graph, then ${\delta }_k(G)\ge 2k$. Further, it is established that the number of vertices in a $\gamma -k$-critical graph $G$ is bounded above by $({\mathrm{\Delta }}_k(G)+1)({\gamma }_k(G)-1)+1$ and that $G$ is a $({\gamma }_k,\ell )$-critical graph if and only if the $k$th power of $G$ is a $(\gamma ,\ell )$-critical graph. It is shown that $(k,\ell )$-critical graphs of arbitrarily large connectivity exist. Moreover, a graph without isolated vertices is shown to be ${\gamma }_k$-critical if and only if each of its blocks is ${\gamma }_k$-critical. Finally it is established that for an integer $\ell \ge 2$, every graph is an induced subgraph of some $({\gamma }_k,\ell )$-critical graph. This paper concludes with some partially answered questions and some open problems.