Upper Bounds on the Domination and Total Domination Number of Fibonacci Cubes

Authors : Elif SAYGI

Pages : 782-785

Doi:10.19113/sdufbed.05851

View : 15 | Download : 13

Publication Date : 2017-08-11

Article Type : Research Paper

Abstract :One of the basic model for interconnection networks is the $n$-dimensional hypercube graph $Q_n$ and the vertices of $Q_n$ are represented by all binary strings of length $n$. The Fibonacci cube $\Gamma_n$ of dimension $n$ is a subgraph of $Q_n$, where the vertices correspond to those without two consecutive 1s in their string representation. In this paper, we deal with the domination number and the total domination number of Fibonacci cubes. First we obtain upper bounds on the domination number of $\Gamma_n$ for $n\ge 13$. Then using these result we obtain upper bounds on the total domination number of $\Gamma_n$ for $n\ge 14$ and we see that these upper bounds improve the bounds given in [1].
Keywords : Fibonacci cube, Domination number, Total domination number