Mutual and total mutual visibility in hypercube-like graphs

Let G be a graph and X ⊆ 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) μ ( G ) (resp. μ t ( G ) ) of G . It is known that computing μ ( G ) is an NP-complete problem, as well as μ t ( G ) . In this paper, we study the (total) mutual-visibility in hypercube-like networks (namely, hypercubes, Fibonacci cubes, cube-connected cycles, and butterflies). Concerning computing μ ( G ) , we provide approximation algorithms for hypercubes, Fibonacci cubes and cube-connected cycles, while we give an exact formula for butterflies. Concerning computing μ t ( G ) (in the literature, already studied in hypercubes), whereas we obtain exact formulae for both cube-connected cycles and butterflies. • We study the mutual-visibility and the total mutual-visibility in hypercube-like graphs. • For a hypercube Q d , we show that ( d ⌊ d 2 ⌋ ) + ( d ⌊ d 2 ⌋ + 3 ) ≤ μ ( Q d ) ≤ 2 d − 1 , and an O ( d ) -approximation algorithm for computing μ ( Q d ) is given. • For a Fibonacci cube Γ d , we provide optimal solutions for μ ( Γ d ) when d ≤ 6 , whereas for larger values of d , we prove μ ( Γ d ) ≤ F d + F d − 2 and μ ( Γ d ) ≥ max 0 ≤ k ≤ ⌈ d 2 ⌉ ⁡ ( d − k + 1 k ) . Furthermore, a 1 ϕ ( ⌈ d 2 ⌉ + 1 ) -approximation algorithm for computing μ ( Γ d ) is given. • For a cube-connected cycle CCC d , we show that 2 ⌈ d 2 ⌉ ≤ μ ( CCC d ) ≤ 3 ⋅ 2 d − 2 . For the total mutual-visibility, μ t ( CCC d ) = 0 . Furthermore, a 3 ⋅ 2 ⌊ d 2 ⌋ − 2 -approximation algorithm for computing μ ( CCC d ) is given. • For a butterfly BF ( d ) , we show that μ ( BF ( d ) ) = 2 d + 1 − 2 and μ t ( B F ( d ) ) = 2 d .