Visibility in hypercubes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910077089218560 |
|---|---|
| author | Axenovich, Maria Liu, Dingyuan |
| author_facet | Axenovich, Maria Liu, Dingyuan |
| contents | 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 $μ(G)$ of a graph $G$ is the largest size of a mutual-visibility set in $G$. Let $n\in\mathbb{N}$ and $Q_{n}$ be an $n$-dimensional hypercube. Cicerone, Di Fonso, Di Stefano, Navarra, and Piselli showed that $2^{n}/\sqrt{n}\leqμ(Q_{n})\leq2^{n-1}$. In this paper, we prove that $μ(Q_{n})>0.186\cdot2^n$ and thus establish that $μ(Q_{n})=Θ(2^{n})$.
We also consider the chromatic mutual-visibility number, $χ_μ(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$. Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero asked whether $χ_μ(Q_{n})=O(1)$. We answer their question in the negative, namely, we show that $χ_μ(Q_{n})$ is a growing function of $n$. Moreover, we show that $χ_μ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04791 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Visibility in hypercubes Axenovich, Maria Liu, Dingyuan Combinatorics 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 $μ(G)$ of a graph $G$ is the largest size of a mutual-visibility set in $G$. Let $n\in\mathbb{N}$ and $Q_{n}$ be an $n$-dimensional hypercube. Cicerone, Di Fonso, Di Stefano, Navarra, and Piselli showed that $2^{n}/\sqrt{n}\leqμ(Q_{n})\leq2^{n-1}$. In this paper, we prove that $μ(Q_{n})>0.186\cdot2^n$ and thus establish that $μ(Q_{n})=Θ(2^{n})$. We also consider the chromatic mutual-visibility number, $χ_μ(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$. Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero asked whether $χ_μ(Q_{n})=O(1)$. We answer their question in the negative, namely, we show that $χ_μ(Q_{n})$ is a growing function of $n$. Moreover, we show that $χ_μ(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. |
| title | Visibility in hypercubes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.04791 |