Visibility in Hypercubes

A subset M of vertices in a graph G is a mutual-visibility set if any two vertices u and v in M “see” each other in G , that is, there exists a shortest u , v -path in G that contains no elements of M as internal vertices. The mutual-visibility number μ (G) μ ( G ) of a graph G is the largest size of a mutual-visibility set in G . Let n∈ N n ∈ N and Qₙ Q n be an n -dimensional hypercube. Cicerone, Di Fonso, Di Stefano, Navarra, and Piselli showed that 2ⁿ/√n≤ μ (Qₙ)≤ 2ⁿ⁻¹ 2 n / n ≤ μ ( Q n ) ≤ 2 n - 1 . In this paper, we prove that μ (Qₙ)>0.186· 2ⁿ μ ( Q n ) > 0.186 · 2 n and thus establish that μ (Qₙ)=Θ (2ⁿ) μ ( Q n ) = Θ ( 2 n ) . We also consider the chromatic mutual-visibility number, χ μ(G) χ μ ( G ) , defined as the smallest number of colors used on vertices of G , such that every color class is a mutual-visibility set in G . Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero asked whether χ μ(Qₙ)=O(1) χ μ ( Q n ) = O ( 1 ) </jats:inline-fo