Mutual Visibility in Hypercube-Like Graphs

Let G be a graph and \(X\subseteq V(G)\) . Then, vertices x and y of G are 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, while X is a total mutual-visibility set if any two vertices from V(G) are X-visible. The cardinality of a largest mutual-visibility set (resp. total mutual-visibility set) is the mutual-visibility number (resp. total mutual-visibility number) \(\mu (G)\) (resp. \(\mu _t(G)\) ) of G. It is known that computing \(\mu (G)\) is an NP-complete problem, as well as \(\mu _t(G)\) . In this paper, we study the (total) mutual-visibility in hypercube-like networks (namely, hypercubes, cube-connected cycles, and butterflies). Concerning computing \(\mu (G)\) , we provide approximation algorithms for both hypercubes and cube-connected cycles, while we give an exact formula for butterflies. Concerning computing \(\mu _t(G)\) (in the literature, already studied in hypercubes), we provide exact formulae for both cube-connected cycles and butterflies.