Domination Parameters Of Star Graph

Abstract

The $n$-star graph $S_n$ is a simple graph whose vertex set is the set of all $n!$ permutations of $\{1,2,\dots ,n\}$ and two vertices $\alpha$ and $\beta$ are adjacent if and only if $\alpha (1)\ne \beta (1)$ and $\alpha (i)\ne \beta (i)$ for exactly one $i$, $i\ne 1$. In the paper, we determine the values of the domination number $\gamma$, the independent domination number ${\gamma }_i$, the perfect domination number ${\gamma }_p$, and we obtain bounds for the total domination number ${\gamma }_t$ and the connected domination number ${\gamma }_c$ for $S_n$.