If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$ and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be $X$-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.


翻译:如果 $X$ 是图 $G$ 的顶点子集,则当存在一个最短的 $u,v$-路径 $P$ 使得 $V(P)\cap X \subseteq \{u,v\}$ 时,称顶点 $u$ 和 $v$ 是 $X$-可见的。如果 $X$ 中任意两个顶点都是 $X$-可见的,则称 $X$ 是一个互不遮挡点集。$G$ 的互不遮挡数是 $G$ 的最大互不遮挡集的基数,并已被研究。在本文中,提出了一些基于 $X$ 中的哪些顶点应该是 $X$-可见的自然对中的互不遮挡问题。这产生了总的、对偶的和外部的互不遮挡数。我们首先展示这些图不变量如何相互关联以及它们与经典互不遮挡数的关系,然后证明了这三个新增的互不遮挡问题的计算难度。根据这个结果,我们计算或估计了几个图形类的值,其中包括网格图和环面图。我们通过为一些特定族群进行的计算,呈现了这些参数值之间的比较。

0
下载
关闭预览

相关内容

【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
129+阅读 · 2021年6月4日
专知会员服务
78+阅读 · 2021年3月16日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Arxiv
0+阅读 · 2023年5月22日
Arxiv
0+阅读 · 2023年5月20日
VIP会员
相关VIP内容
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
129+阅读 · 2021年6月4日
专知会员服务
78+阅读 · 2021年3月16日
因果图,Causal Graphs,52页ppt
专知会员服务
253+阅读 · 2020年4月19日
相关资讯
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
Top
微信扫码咨询专知VIP会员