Total mutual-visibility in Hamming graphs

Csilla Bujtás
Sandi Klavžar
Jing Tian

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 the shortest \(x,y\)-path \(P\) with \(V(P) \cap X \subseteq \{x,y\}\). The cardinality of the largest total mutual-visibility set of \(G\) is the total mutual-visibility number \(\mu_{\rm 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_{\rm t}(K_{n_1}\square K_{n_2}\square K_{n_3})\) are determined. It is proved that \(\mu_{\rm t}(K_{n_1} \square \cdots \square K_{n_r}) = O(N^{r-2})\), where \(N = n_1+\cdots + n_r\), and that \(\mu_{\rm t}(K_s^{\square r}) = \Theta(s^{r-2})\) for every \(r \geq 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.

Keywords: mutual-visibility set, total mutual-visibility set, Hamming graph, Turán-type problem.

Mathematics Subject Classification: 05C12, 05C38, 05C65, 05C76.

Full text (pdf)