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 (formula presented) 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 μ(G) of G. In general, computing μ(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 μ(G) in Fibonacci Cubes.