Total mutual-visibility in Hamming graphs

Abstract

If $G$ is a graph and $X\subseteq V(G)$, then $X$ is a total mutual-visibility set if every pair of vertices $x$ and $y$ of $G$ admits a shortest $x,y$-path $P$ with $V(P)\cap X\subseteq \{x,y\}$. The cardinality of a largest total mutual-visibility set of $G$ is the total mutual-visibility number ${\mu }_{\mathrm{t}}(G)$ of $G$. In this paper the total mutual-visibility number is studied on Hamming graphs, that is, Cartesian products of complete graphs. Different equivalent formulations for the problem are derived. The values ${\mu }_{\mathrm{t}}(K_{n_1}\square K_{n_2}\square K_{n_3})$ are determined. It is proved that ${\mu }_{\mathrm{t}}(K_{n_1}\square \cdots \square K_{n_r})=O(N^{r-2})$, where $N=n_1+\cdots +n_r$, and that ${\mu }_{\mathrm{t}}(K_s^{\square ,r})=\Theta (s^{r-2})$ for every $r\ge 3$, where $K_s^{\square ,r}$ denotes the Cartesian product of $r$ copies of $K_s$. The main theorems are also reformulated as Turán-type results on hypergraphs.

Cited by in corpus (1)

• Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets