Mutual-Visibility in Fibonacci Cubes

Hypercubes, Butterfly and other well-structured topologies represent intriguing challenges in computer network architectures, especially for parallel and distributed computations. Within such a context, mutual-visibility plays a central role for communication activities. Given a graph \(G=(V,E)\) and a subset X of its vertices, x and y \(\in V\) are said to be X-visible if there exists a shortest x, y-path where no internal vertices belong to X. The set X is a mutual-visibility set of G if every two vertices of X are X-visible. The cardinality of a largest mutual-visibility set is the mutual-visibility number \(\mu (G)\) of G. In general, computing \(\mu (G)\) is NP-complete. In this paper, we study the mutual-visibility in Fibonacci Cube networks, a variant of the Hypercube topology with various interesting properties. In particular, we provide an approximation algorithm for computing \(\mu (G)\) in Fibonacci Cubes.