Variety of mutual-visibility problems in hypercubes

被引:0
|
作者
Korze, Danilo [1 ]
Vesel, Aleksander [2 ]
机构
[1] Univ Maribor, Fac Elect Engn & Comp Sci, Koroska Cesta 46, SI-2000 Maribor, Slovenia
[2] Univ Maribor, Fac Nat Sci & Math, Koroska Cesta 160, SI-2000 Maribor, Slovenia
关键词
Mutual visibility; Hypercube; Binary code; ROBOTS;
D O I
10.1016/j.amc.2024.129218
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a graph and M c V(G). Vertices x, y E Mare M-visible if there exists a shortest x, y-path of G that does not pass through any vertex of M \ {x,y}. We say that M is a mutual-visibility set if each pair of vertices of M is M-visible, while the size of any largest mutual-visibility set of G is the mutual-visibility number of G. If some additional combinations for pairs of vertices x, y are required to be M-visible, we obtain the total (every x, y E V(G) are M-visible), the outer (every x E M and every y E V(G) \ M are M-visible), and the dual (every x, y E V(G) \ M are M-visible) mutual-visibility set of G. The cardinalities of the largest of the above defined sets are known as the total, the outer, and the dual mutual-visibility number of G, respectively. We present results on the variety of mutual-visibility problems in hypercubes.
引用
收藏
页数:10
相关论文
共 31 条
  • [21] Problems on routing hounded distance assignments in hypercubes
    Bagherzadeh, N
    Dowd, M
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 1996, 11 (04): : 221 - 226
  • [22] Mutual visibility of luminous robots despite angular inaccuracy
    Pramanick, Subhajit
    Jana, Saswata
    Bhattacharya, Adri
    Mandal, Partha Sarathi
    THEORETICAL COMPUTER SCIENCE, 2024, 1011
  • [23] Mutual visibility by fat robots with slim omnidirectional camera
    Bose, Kaustav
    Chakraborty, Abhinav
    Mukhopadhyaya, Krishnendu
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2023, 180
  • [24] An Optimal Algorithm for Geodesic Mutual Visibility on Hexagonal Grids
    Badri, Sahar
    Cicerone, Serafino
    Di Fonso, Alessia
    Di Stefano, Gabriele
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2024, 2025, 14931 : 161 - 176
  • [25] Fault-tolerant mutual visibility without any axis agreement in presence of mobility failure
    Pramanick, Subhajit
    Jana, Saswata
    Mandal, Partha Sarathi
    THEORETICAL COMPUTER SCIENCE, 2025, 1025
  • [26] On the mutual visibility in Cartesian products and triangle-free graphs
    Cicerone, Serafino
    Di Stefano, Gabriele
    Klavzar, Sandi
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 438
  • [27] Optimum Algorithm for Mutual Visibility Among Asynchronous Robots with Lights
    Bhagat, Subhash
    Mukhopadhyaya, Krishnendu
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2017, 2018, 10616 : 341 - 355
  • [28] The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees
    Cicerone, Serafino
    Di Fonso, Alessia
    Di Stefano, Gabriele
    Navarra, Alfredo
    PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, ICDCN 2023, 2023, : 150 - 159
  • [29] The geodesic mutual visibility problem: Oblivious robots on grids and trees
    Cicerone, Serafino
    Di Fonso, Alessia
    Di Stefano, Gabriele
    Navarra, Alfredo
    PERVASIVE AND MOBILE COMPUTING, 2023, 95
  • [30] Mutual Visibility with ASYNC Luminous Robots Having Inaccurate Movements
    Pramanick, Subhajit
    Jana, Saswata
    Bhattacharya, Adri
    Mandal, Partha Sarathi
    ALGORITHMICS OF WIRELESS NETWORKS, ALGOWIN 2023, 2023, 14061 : 41 - 57