.png){kind=icon}
.png){kind=icon}
Return
Visibility in Hypercubes
.png){kind=icon}
PRE
AI
DOI：10.1007/s00373-026-03025-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A subset M of vertices in a graph G is a mutual-visibility set if any two vertices u and v in M see each other in G, that is, there exists a shortest u, v-path in G that contains no elements of M as internal vertices. The mutual-visibility number & micro;(G) of a graph G is the largest size of a mutual-visibility set in G. Let n E N and Q(n)be an ndimensional hypercube. Cicerone, Di Fonso, Di Stefano, Navarra, and Piselli showed that 2(n)//n < & micro;(Q(n)) < 2(n-1).In this paper, we prove that & micro;(Q(n)) > 0.186 & centerdot; 2(n)and thus establish that & micro;(Q(n)) = Theta(2(n)). We also consider the chromatic mutual-visibility number, chi(& micro;) (G), defined as the smallest number of colors used on vertices of G, such that every color class is a mutual-visibility set in G. Klavzar, Kuziak, Valenzuela-Tripodoro, and Yero asked whether chi & micro; (Q(n)) = O(1). We answer their question in the negative, namely, we show that chi(& micro;)(Q(n)) is a growing function of n. Moreover, we show that chi(& micro;)(Q(n)) = O(log log n). Finally, we study the so-called total mutual-visibility number of graphs and give asymptotically tight bounds on this parameter for hypercubes.
Keywords:
Visibility
Mutual-visibility
Hypercubes
Daisies