On domination-type invariants of Fibonacci cubes and hypercubes
Jernej Azarija, Sandi Klavžar, Yoomi Rho, Seung-Bo Sim · Ars Mathematica Contemporanea · 2017
The Fibonacci cube Γn is the subgraph of the n-dimensional cube Qn 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) ≤ 2Fn − 10 + 21Fn − 8 holds for n ≥ 11, where Fn are the Fibonacci numbers. It is proved that if n ≥ 9, then γt(Γn) ≥ ⌈(Fn + 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(Qn)=2n − 2 holds for n ≥ 6 is also disproved in several ways.