The Domination Number of Fibonacci Cubes

Abstract

A dominating set is a vertex subset $D$ of a graph $G$ such that each vertex of $G$ is either in $D$ or adjacent to a vertex in $D$. The domination number, $\gamma (G)$, is the minimum cardinality of a dominating set of a graph $G$. In this paper, we will investigate the domination number of Fibonacci cubes. We firstly study the degree sequence of the Fibonacci cubes. Then, a lower bound for the domination number of Fibonacci cube of order $n$ is obtained, and the exact value of the domination number of Fibonacci cubes of order at most $8$ is determined.