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.