.png){kind=icon}
返回
Visibility in Hypercubes
.png){kind=icon}
PRE
AI
DOI：10.1007/s00373-026-03025-9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
图G中顶点的一个子集M是互可视集，如果G中任意两个顶点u和v在M中相互可见，即G中存在一条不包含M作为内部顶点的最短u-v路径。图G的互可视数& micro;(G)是G中互可视集的最大大小。设n ∈ N，Q(n)为n维超立方体。Cicerone、Di Fonso、Di Stefano、Navarra和Piselli证明了2(n)//n < & micro;(Q(n)) < 2(n-1)。在本文中，我们证明& micro;(Q(n)) > 0.186 & centerdot; 2(n)，从而确立& micro;(Q(n)) = Θ(2(n))。我们还考虑了着色互可视数chi(& micro;) (G)，定义为G中顶点着色的最小颜色数，使得每个颜色类都是G中的互可视集。Klavzar、Kuziak、Valenzuela-Tripodoro和Yero询问是否chi & micro; (Q(n)) = O(1)。我们对此问题给予否定回答，即我们证明chi(& micro;)(Q(n))是n的增函数。此外，我们证明chi(& micro;)(Q(n)) = O(log log n)。最后，我们研究所谓的图的完全互可视数，并给出超立方体上此参数的渐近紧界。
Keyword:
Visibility
Mutual-visibility
Hypercubes
Daisies
