Visibility in Hypercubes

Abstract 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/n (Q₍) 2^n-1 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^n) μ (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