\(K_n\)-Domination Sequences of Graphs

The domination number \(\gamma(G)\) and the total domination number \(\gamma_t(G)\) of a graph are generalized to the \(K_n\)-domination number \(\gamma_{k_n}(G)\) and the total \(K_n\)-domination number \(\gamma_{K_n}^t(G)\) for \(n \geq 2\), where \(\gamma(G) = \gamma_{K_2}(G)\) and \(\gamma_t(G) = \gamma_{K_2}^t(G)\). A nondecreasing sequence \(a_2, a_3, \ldots, a_m\) of positive integers is said to be a \(K_n\)-domination (total \(K_n\)-domination, respectively) sequence if it can be realized as the sequence of generalized domination (total domination, respectively) numbers \(\gamma_{K_2}(G), \gamma_{K_3}(G), \ldots, \gamma_{K_m}(G)\) (\(\gamma_{K_2}^t(G), \gamma_{K_3}^t(G), \ldots, \gamma_{K_m}^t(G)\), respectively) of some graph \(G\). It is shown that every nondecreasing sequence \(a_2, a_3, \ldots, a_m\) of positive integers is a \(K_n\)-domination sequence (total \(K_n\)-domination sequence, if \(a_2 \geq 2\), respectively). Further, the minimum order of a graph \(G\) with \(a_2, a_3, \ldots, a_m\) as a \(K_n\)-domination sequence is determined. \(K_n\)-connectivity is defined and for \(a_2 \geq 2\) we establish the existence of a \(K_m\)-connected graph with \(a_2, a_3, \ldots, a_m\) as a \(K_n\)-domination sequence for every nondecreasing sequence \(a_2, a_3, \ldots, a_m\) of positive integers.