On domination-type invariants of Fibonacci cubes and hypercubes

Abstract

The Fibonacci cube Γ_n is the subgraph of the n-dimensional cube Q_n induced by the vertices that contain no two consecutive 1s. Using integer linear programming, exact values are obtained for γ_t(Γ_n), n ≤ 12. Consequently, γ_t(Γ_n) ≤ 2F_n − 10 + 21F_n − 8 holds for n ≥ 11, where F_n are the Fibonacci numbers. It is proved that if n ≥ 9, then γ_t(Γ_n) ≥ ⌈(F_n + 2−11)/(n−3)⌉ − 1. Using integer linear programming exact values for the 2-packing number, connected domination number, paired domination number, and signed domination number of small Fibonacci cubes and hypercubes are obtained. A conjecture on the total domination number of hypercubes asserting that γ_t(Q_n)=2^n − 2 holds for n ≥ 6 is also disproved in several ways.