Menu
For \(k \geq 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 \geq 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) \leq k\}\) and let \(\delta_k(G) = \min\{|N_k(v)|: v \in V\}\) and let \(\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) \geq 2k\). Further, it is established that the number of vertices in a \(\gamma-k\)-critical graph \(G\) is bounded above by \((\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 \geq 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.