On domination-type invariants of Fibonacci cubes and hypercubes

Jernej Azarija, Sandi Klavžar, Yoomi Rho, Seungbo Sim


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 γtn), n ≤ 12. Consequently, γtn) ≤ 2Fn − 10 + 21Fn − 8 holds for n ≥ 11, where Fn are the Fibonacci numbers. It is proved that if n ≥ 9, then γtn) ≥ ⌈(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.


Total domination number, Fibonacci cube, hypercube, integer linear programming, covering codes

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1172.bae

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications