Visibility in Hypercubes

Source abstract

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 $$\mu (G)$$ μ ( G ) of a graph G is the largest size of a mutual-visibility set in G . Let $$n\in \mathbb {N}$$ n ∈ N and $$Q_{n}$$ Q n be an n -dimensional hypercube. Cicerone, Di Fonso, Di Stefano, Navarra, and Piselli showed that $$2^{n}/\sqrt{n}\le \mu (Q_{n})\le 2^{n-1}$$ 2 n / n ≤ μ ( Q n ) ≤ 2 n - 1 . In this paper, we prove that $$\mu (Q_{n})>0.186\cdot 2^n$$ μ ( Q n ) > 0.186 · 2 n and thus establish that $$\mu (Q_{n})=\Theta (2^{n})$$ μ ( Q n ) = Θ ( 2 n ) . We also consider the chromatic mutual-visibility number, $$\chi _{\mu }(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 $$\chi _{\mu }(Q_{n})=O(1)$$ χ μ ( Q n ) = O ( 1 ) . We answer their question in the negative, namely, we show that $$\chi _{\mu }(Q_{n})$$ χ μ ( Q n ) is a growing function of n . Moreover, we show that $$\chi _{\mu }(Q_{n})=O(\log \log {n})$$ χ μ ( Q n ) = O ( log log n ) . Finally, we study the so-called total mutual-visibility number of graphs and give asymptotically tight bounds on this parameter for hypercubes.