| Naslov: | Lower (total) mutual-visibility number in graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Yero, Ismael G. (Avtor) |
|---|
| Datoteke: |  URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0096300323005805
 PDF - Predstavitvena datoteka, prenos (567,18 KB)
MD5: 512C343BEADD072ECB570FDFE0379EA2
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | Given a graph $G$, a set $X$ of vertices in $G$ satisfying that between every two vertices in $X$ (respectively, in $G$) there is a shortest path whose internal vertices are not in $X$ is a mutual-visibility (respectively, total mutual-visibility) set in $G$. The cardinality of a largest (total) mutual-visibility set in $G$ is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in $G$, and denote them by $\mu^{-}(G)$ and $\mu_t^{-}(G)$, respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph $G$, we prove that both differences $\mu^{-}(G)-\mu_t^{-}(G)$ and $\mu_t^{-}(G)-\mu^{-}(G)$ can be arbitrarily large. We characterize graphs $G$ with some small values of $\mu^{-}(G)$ and $\mu_t^{-}(G)$, and prove a useful tool called the Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with the Bollobás-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to $\mu_t^{-}(G)$. |
|---|
| Ključne besede: | mutual-visibility set, mutual-visibility number, total mutual-visibility set, computational complexity |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.03.2024 |
|---|
| Leto izida: | 2024 |
|---|
| Št. strani: | 11 str. |
|---|
| Številčenje: | Vol. 465, article no. 128411 |
|---|
| PID: | 20.500.12556/DiRROS-18205  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0096-3003 |
|---|
| DOI: | 10.1016/j.amc.2023.128411 |
|---|
| COBISS.SI-ID: | 169849091 |
|---|
| Datum objave v DiRROS: | 19.02.2024 |
|---|
| Število ogledov: | 147 |
|---|
| Število prenosov: | 65 |
|---|
| Metapodatki: |     |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
