$K_n$-Domination Sequences of Graphs

Abstract

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\ge 2$, where $\gamma (G)={\gamma }_{K_2}(G)$ and ${\gamma }_t(G)={\gamma }_{K_2}^t(G)$. A nondecreasing sequence $a_2,a_3,\dots ,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),\dots ,{\gamma }_{K_m}(G)$ (${\gamma }_{K_2}^t(G),{\gamma }_{K_3}^t(G),\dots ,{\gamma }_{K_m}^t(G)$, respectively) of some graph $G$. It is shown that every nondecreasing sequence $a_2,a_3,\dots ,a_m$ of positive integers is a $K_n$-domination sequence (total $K_n$-domination sequence, if $a_2\ge 2$, respectively). Further, the minimum order of a graph $G$ with $a_2,a_3,\dots ,a_m$ as a $K_n$-domination sequence is determined. $K_n$-connectivity is defined and for $a_2\ge 2$ we establish the existence of a $K_m$-connected graph with $a_2,a_3,\dots ,a_m$ as a $K_n$-domination sequence for every nondecreasing sequence $a_2,a_3,\dots ,a_m$ of positive integers.