Total mutual-visibility in Hamming graphs

• Autorzy: Bujtás Csilla , Klavžar Sandi , Tian Jing

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.63

• Języki publikacji: EN

Abstrakty

EN

If G is a graph and X ⊆ 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) ∩ X ⊆ {x, y}. The cardinality of the largest total mutual-visibility set of G is the total mutual-visibility number μ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 μt(Kn1 □Kn2 □Kn3 ) are determined. It is proved that μt(Kn1 □ · · · □Knr ) = O(Nr−2), where N = n1 + · · · + nr, and that μt(Ks□,r) = Θ(sr−2) for every r ≥ 3, where Ks□,r denotes the Cartesian product of r copies of Ks. The main theorems are also reformulated as Turán-type results on hypergraphs.

Słowa kluczowe

EN

mutual-visibility set; total mutual-visibility set; Hamming graph; Turán-type problem

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 63--78
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Bujtás Csilla

• University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia
• Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

• https://orcid.org/0000-0002-0511-5291

autor

Klavžar Sandi

• University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia
• Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
• University of Maribor, Faculty of Natural Sciences and Mathematics, Maribor, Slovenia

• https://orcid.org/0000-0002-1556-4744

autor

Tian Jing

• Zhejiang University of Science and Technology, School of Science, Hangzhou, Zhejiang 310023, PR China
• Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

• https://orcid.org/0000-0002-1578-4798

Bibliografia

• [1] R. Adhikary, K. Bose, M.K. Kundu, B. Sau, Mutual visibility on grid by asynchronous luminous robots, Theoret. Comput. Sci. 922 (2022), 218–247.
• [2] W.G. Brown, P. Erdős, V.T. Sós, Some extremal problems on r-graphs, [in:] New directions in the theory of graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, Academic Press, New York, 1973, 55–63.
• [3] S. Cicerone, A. Di Fonso, G. Di Stefano, A. Navarra, The geodesic mutual visibility problem for oblivious robots: the case of trees, [in:] 24th International Conference on Distributed Computing and Networking, ACM, 2023, 150–159.
• [4] S. Cicerone, G. Di Stefano, S. Klavžar, On the mutual-visibility in Cartesian products and in triangle-free graphs, Appl. Math. Comput. 438 (2023), 127619.
• [5] S. Cicerone, G. Di Stefano, S. Klavžar, I.G. Yero, Mutual-visibility in strong products of graphs via total mutual-visibility, Discrete Appl. Math. 121 (2024), 136–146.
• [6] G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, G. Viglietta, Mutual visibility by luminous robots without collisions, Inform. and Comput. 254 (2017), 392–418.
• [7] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022), 126850.
• [8] D. Gerbner, B. Patkós, Extremal Finite Set Theory, CRC Press, Boca Raton, FL, 2019.
• [9] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
• [10] P. Keevash, Hypergraph Turán problems, [in:] Surveys in Combinatorics, Cambridge University Press, 2011, 83–139.
• [11] D. Kuziak, J.A. Rodríguez-Velázquez, Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products, Bull. Malays. Math. Sci. Soc. 46 (2023), 197.
• [12] P. Poudel, A. Aljohani, G. Sharma, Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement, Theoret. Comput. Sci. 850 (2021), 116–134.
• [13] J. Tian, S. Klavžar, Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products, Discuss. Math. Graph Theory 44 (2024), 1277–1291.
• [14] D.B. West, Combinatorial Mathematics, Cambridge University Press, Cambridge, 2021.
• [15] K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951), 301.