Visibility in Hypercubes

Maria Axenovich, Dingyuan Liu

Published 2024-02-07Version 1

A set $\mathcal{X}$ of vertices in a graph $G$ is a mutual-visibility set if any two vertices $u$ and $v$ in $\mathcal{X}$ "see" each other in $G$, that is, there exists a shortest $u$-$v$ path in $G$ that contains no elements of $\mathcal{X}$ as internal vertices. The mutual-visibility number of a graph $G$, denoted $\mu(G)$, is the largest size of a mutual-visibility set in $G$. This notion was introduced by Di Stefano and studied for various product graphs, particularly hypercubes, motivated by communication analysis in networks. Cicerone, Fonso, Di Stefano, Navarra, and Piselli showed that $2^{n}/\sqrt{n}\leqslant\mu(Q_{n})\leqslant2^{n-1}$. We prove that $\mu(Q_{n})\geqslant0.186\cdot2^n$ using a breakthrough result on daisy-free hypergraphs by Ellis, Ivan, and Leader. We also consider so-called total mutual-visibility number for graphs and give asymptotically tight bounds on this parameter for hypercubes.