Abstract
Let G be a graph and \(X\subseteq V(G)\). Then, vertices x and y of G are X-visible if there exists a shortest x, y-path where no internal vertices belong to X. The set X is a mutual-visibility set of G if every two vertices of X are X-visible, while X is a total mutual-visibility set if any two vertices from V(G) are X-visible. The cardinality of a largest mutual-visibility set (resp. total mutual-visibility set) is the mutual-visibility number (resp. total mutual-visibility number) \(\mu (G)\) (resp. \(\mu _t(G)\)) of G. It is known that computing \(\mu (G)\) is an NP-complete problem, as well as \(\mu _t(G)\). In this paper, we study the (total) mutual-visibility in hypercube-like networks (namely, hypercubes, cube-connected cycles, and butterflies). Concerning computing \(\mu (G)\), we provide approximation algorithms for both hypercubes and cube-connected cycles, while we give an exact formula for butterflies. Concerning computing \(\mu _t(G)\) (in the literature, already studied in hypercubes), we provide exact formulae for both cube-connected cycles and butterflies.
The work has been supported in part by the European Union - NextGenerationEU under the Italian Ministry of University and Research (MUR) National Innovation Ecosystem grant ECS00000041 - VITALITY - CUP J97G22000170005, and by the Italian National Group for Scientific Computation (GNCS-INdAM).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
References
Bose, K., Kundu, M.K., Adhikary, R., Sau, B.: Optimal gathering by asynchronous oblivious robots in hypercubes. In: Gilbert, S., Hughes, D., Krishnamachari, B. (eds.) ALGOSENSORS 2018. LNCS, vol. 11410, pp. 102–117. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14094-6_7
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)
Bujtá, C., Klavžar, S., Tian, J.: Total mutual-visibility in hamming graphs (2023). https://arxiv.org/abs/2307.05168
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem for oblivious robots: the case of trees. In: 24th International Conference on Distributed Computing and Networking, ICDCN 2023, pp. 150–159. ACM (2023). https://doi.org/10.1145/3571306.3571401
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem: oblivious robots on grids and trees. Pervasive Mob. Comput. 95, 101842 (2023). https://doi.org/10.1016/j.pmcj.2023.101842. https://www.sciencedirect.com/science/article/pii/S1574119223001001
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: Time-optimal geodesic mutual visibility of robots on grids within minimum area. In: Dolev, S., Schieber, B. (eds.) SSS 2023. LNCS, vol. 14310, pp. 385–399. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-44274-2_29
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A., Piselli, F.: Mutual visibility in hypercube-like graphs (2023). https://arxiv.org/abs/2308.14443
Cicerone, S., Di Stefano, G.: Mutual-visibility in distance-hereditary graphs: a linear-time algorithm. In: Fernandes, C.G., Rajsbaum, S. (eds.) Proceedings of the XII Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023, Huatulco, Mexico, 18–22 September 2023. Procedia Computer Science, vol. 223, pp. 104–111. Elsevier (2023). https://doi.org/10.1016/J.PROCS.2023.08.219
Cicerone, S., Di Stefano, G., Droždek, L., Hedžet, J., Klavžar, S., Yero, I.G.: Variety of mutual-visibility problems in graphs. Theor. Comput. Sci. 974, 114096 (2023). https://doi.org/10.1016/j.tcs.2023.114096
Cicerone, S., Di Stefano, G., Klavžar, S.: On the mutual visibility in cartesian products and triangle-free graphs. Appl. Math. Comput. 438, 127619 (2023). https://doi.org/10.1016/j.amc.2022.127619
Cicerone, S., Di Stefano, G., Klavžar, S., Yero, I.G.: Mutual-visibility in strong products of graphs via total mutual-visibility (2022). https://arxiv.org/abs/2210.07835
Cicerone, S., Di Stefano, G., Navarra, A.: Gathering robots in graphs: the central role of synchronicity. Theor. Comput. Sci. 849, 99–120 (2021). https://doi.org/10.1016/j.tcs.2020.10.011
Cicerone, S., Di Stefano, G., Klavžar, S., Yero, I.G.: Mutual-visibility problems on graphs of diameter two (2024). https://arxiv.org/abs/2401.02373
D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610, 158–168 (2016)
D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering on rings under the look-compute-move model. Distrib. Comput. 27(4), 255–285 (2014)
D’Angelo, G., Navarra, A., Nisse, N.: A unified approach for gathering and exclusive searching on rings under weak assumptions. Distrib. Comput. 30(1), 17–48 (2017)
Di Luna, G.A., Flocchini, P., Chaudhuri, S.G., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions. Inf. Comput. 254, 392–418 (2017). https://doi.org/10.1016/j.ic.2016.09.005
Di Stefano, G.: Mutual visibility in graphs. Appl. Math. Comput. 419, 126850 (2022). https://doi.org/10.1016/j.amc.2021.126850
Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distrib. Comput. 30(2), 75–86 (2017)
Dudeney, H.E.: Amusements in Mathematics. Nelson, Edinburgh (1917)
Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411, 3235–3246 (2010)
Klavzar, S., Neethu, P.K., Chandran, S.V.U.: The general position achievement game played on graphs. Discret. Appl. Math. 317, 109–116 (2022). https://doi.org/10.1016/j.dam.2022.04.019
Klavžar, S., Tian, J.: Graphs with total mutual-visibility number zero and total mutual-visibility in cartesian products. Discussiones Mathematicae Graph Theory (2023). https://doi.org/10.7151/dmgt.2496
Kuziak, D., Rodríguez-Velázquez, J.A.: Total mutual-visibility in graphs with emphasis on lexicographic and cartesian products (2023). https://arxiv.org/abs/2306.15818
Manuel, P.D., Abd-El-Barr, M.I., Rajasingh, I., Rajan, B.: An efficient representation of Benes networks and its applications. J. Discret. Algorithms 6(1), 11–19 (2008). https://doi.org/10.1016/j.jda.2006.08.003
Manuel, P.D., Klavzar, S.: The graph theory general position problem on some interconnection networks. Fundam. Informaticae 163(4), 339–350 (2018). https://doi.org/10.3233/FI-2018-1748
Navarra, A., Piselli, F.: Mutual-visibility in Fibonacci cubes. In: Barolli, L. (ed.) AINA 2024. LNDECT, vol. 199, pp. 22–33. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-57840-3_3
Poudel, P., Aljohani, A., Sharma, G.: Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement. Theor. Comput. Sci. 850, 116–134 (2021). https://doi.org/10.1016/j.tcs.2020.10.033
Prabha, R., Devi, S.R., Manuel, P.: General position problem of butterfly networks (2023). https://arxiv.org/abs/2302.06154
Sharma, G., Vaidyanathan, R., Trahan, J.L.: Optimal randomized complete visibility on a grid for asynchronous robots with lights. Int. J. Netw. Comput. 11(1), 50–77 (2021)
Stirling, J., Holliday, F.: The Differential Method: Or, A Treatise Concerning Summation and Interpolation of Infinite Series. E. Cave (1749)
Van, D., Marilynn, W., Quentin, L., Stout, Q.: Perfect dominating sets on cube-connected cycles. Congr. Numer. 97, 51–70 (1993)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A., Piselli, F. (2024). Mutual Visibility in Hypercube-Like Graphs. In: Emek, Y. (eds) Structural Information and Communication Complexity. SIROCCO 2024. Lecture Notes in Computer Science, vol 14662. Springer, Cham. https://doi.org/10.1007/978-3-031-60603-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-60603-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60602-1
Online ISBN: 978-3-031-60603-8
eBook Packages: Computer ScienceComputer Science (R0)