Total mutual-visibility in Hamming graphs

Bujtás, Csilla (author), Klavžar, Sandi (author), Tian, Jing (author)

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_{\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\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.

• Language: English
• Keywords: mutual-visibility set, total mutual-visibility set, Hamming graphs, Turán-type problem
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: Str. 63-78
• Numbering: Vol. 45, no. 1
• PID: 20.500.12556/RUL-166274
• UDC: 519.17
• ISSN on article: 1232-9274
• DOI: 10.7494/OpMath.2025.45.1.63
• COBISS.SI-ID: 220652803
• Publication date in RUL: 30.12.2024

Record is a part of a journal

• Title: Rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica : Opuscula Mathematica
• Shortened title: Rocz. Akad. Gór.-Hut. im. Stanisława Staszica, Opusc. Math.
• Publisher: AGH University of Science and Technology Press
• ISSN: 1232-9274
• COBISS.SI-ID: 16179545

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: množica vzajemne vidnosti, množica celotne vzajemne vidnosti, Hammingovi grafi, problem Turánovega tipa