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 $$\mu (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>μ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of a graph G is the largest size of a mutual-visibility set in G . Let $$n\in \mathbb {N}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> and $$Q_{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>/</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo>≤</mml:mo> <mml:mi>μ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> . In this paper, we prove that $$\mu (Q_{n})&gt;0.186\cdot 2^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>μ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mn>0.186</mml:mn> <mml:mo>·</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> and thus establish that $$\mu (Q_{n})=\Theta (2^{n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>μ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . We also consider the chromatic mutual-visibility number, $$\chi _{\mu }(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:mi>μ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:mi>μ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>Q</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> </jats:inline-fo