Mutual-Visibility Sets in Cartesian Products of Paths and Cycles

被引:3
|
作者
Korze, Danilo [1 ]
Vesel, Aleksander [2 ]
机构
[1] Univ Maribor, Fac Elect Engn & Comp Sci, Koroska Cesta 46, Maribor 2000, Slovenia
[2] Univ Maribor, Fac Nat Sci & Math, Koroska Cesta 160, Maribor 2000, Slovenia
关键词
Mutual-visibility set; mutual-visibility number; Cartesian product; ROBOTS;
D O I
10.1007/s00025-024-02139-x
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For a given graph G, the mutual-visibility problem asks for the largest set of vertices M subset of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M \subseteq V(G)$$\end{document} with the property that for any pair of vertices u,v is an element of M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u,v \in M$$\end{document} there exists a shortest u, v-path of G that does not pass through any other vertex in M. The mutual-visibility problem for Cartesian products of a cycle and a path, as well as for Cartesian products of two cycles, is considered. Optimal solutions are provided for the majority of Cartesian products of a cycle and a path, while for the other family of graphs, the problem is completely solved.
引用
收藏
页数:20
相关论文
共 50 条
  • [21] Extending partial edge colorings of iterated cartesian products of cycles and paths
    Casselgren, Carl Johan
    Granholm, Jonas B.
    Petros, Fikre B.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2024, 26 (02) : 1 - 10
  • [22] On strict-double-bound graphs and Cartesian products of paths and cycles
    Egawa, Yoshimi
    Ogawa, Kenjiro
    Ozeki, Kenta
    Tagusari, Satoshi
    Tsuchiya, Morimasa
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (05)
  • [23] The secure domination number of Cartesian products of small graphs with paths and cycles
    Haythorpe, Michael
    Newcombe, Alex
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 32 - 45
  • [24] Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs
    Shasha Ma
    Liancui Zuo
    Journal of Combinatorial Optimization, 2016, 32 : 725 - 740
  • [25] Equitable colorings of Cartesian products of square of cycles and paths with complete bipartite graphs
    Ma, Shasha
    Zuo, Liancui
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (03) : 725 - 740
  • [26] Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
    Cicerone, Serafino
    Di Stefano, Gabriele
    XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 104 - 111
  • [27] On the outer independent 2-rainbow domination number of Cartesian products of paths and cycles
    Dehgardi, Nasrin
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2021, 6 (02) : 315 - 324
  • [28] Rainbow Domination in Cartesian Product of Paths and Cycles
    Gao, Hong
    Zhang, Yunlei
    Wang, Yuqi
    Guo, Yuanyuan
    Liu, Xing
    Liu, Renbang
    Xi, Changqing
    Yang, Yuansheng
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2024, 35 (08) : 907 - 928
  • [29] On the crossing numbers of Cartesian products with paths
    Bokal, Drago
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (03) : 381 - 384
  • [30] Decycling Cartesian products of two cycles
    Pike, DA
    Zou, YB
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 19 (03) : 651 - 663