Visibility in graphs under edge and vertex removal
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909622487482368 |
|---|---|
| author | Dokyeesun, Pakanun Bujtás, Csilla |
| author_facet | Dokyeesun, Pakanun Bujtás, Csilla |
| contents | For a connected graph $G$ and $X\subseteq V(G)$, we say that two vertices $u$, $v$ are $X$-visible if there is a shortest $u,v$-path $P$ with $V(P)\cap X \subseteq \{u,v\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set in $G$. The largest cardinality of such a set in $G$ is the mutual-visibility number $μ(G)$. When the visibility constraint is extended to further types of vertex pairs, we get the definitions of outer, dual, and total mutual-visibility sets and the respective graph invariants $μ_o(G)$, $μ_d(G)$, and $μ_t(G)$.
This work concentrates on the possible changes in the four visibility invariants when an edge $e$ or a vertex $x$ is removed from $G$ and the graph remains connected. It is proved that $\frac{1}{2}μ(G) \le μ(G-e) \le 2μ(G)$ and $\frac{1}{6}μ_o(G) \le μ_o(G-e) \le 2μ_o(G)+1$ hold for every graph. Further general upper bounds established here are $μ_t(G-e) \leq μ_t(G)+2$ and $μ(G-x) \leq 2μ(G)$. For all but one of the remaining cases, it is shown that the visibility invariant may increase or decrease arbitrarily under the considered local operation. For example, neither $μ_d(G-e)$ nor $μ_d(G-x)$ allows lower or upper bounds of the form $a \cdot μ_d(G)+b$ with a positive constant $a$. Along the way, the realizability of the four visibility invariants in terms of the order is also characterized in the paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19340 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Visibility in graphs under edge and vertex removal Dokyeesun, Pakanun Bujtás, Csilla Combinatorics 05C12, 05C31, 05C69 For a connected graph $G$ and $X\subseteq V(G)$, we say that two vertices $u$, $v$ are $X$-visible if there is a shortest $u,v$-path $P$ with $V(P)\cap X \subseteq \{u,v\}$. If every two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set in $G$. The largest cardinality of such a set in $G$ is the mutual-visibility number $μ(G)$. When the visibility constraint is extended to further types of vertex pairs, we get the definitions of outer, dual, and total mutual-visibility sets and the respective graph invariants $μ_o(G)$, $μ_d(G)$, and $μ_t(G)$. This work concentrates on the possible changes in the four visibility invariants when an edge $e$ or a vertex $x$ is removed from $G$ and the graph remains connected. It is proved that $\frac{1}{2}μ(G) \le μ(G-e) \le 2μ(G)$ and $\frac{1}{6}μ_o(G) \le μ_o(G-e) \le 2μ_o(G)+1$ hold for every graph. Further general upper bounds established here are $μ_t(G-e) \leq μ_t(G)+2$ and $μ(G-x) \leq 2μ(G)$. For all but one of the remaining cases, it is shown that the visibility invariant may increase or decrease arbitrarily under the considered local operation. For example, neither $μ_d(G-e)$ nor $μ_d(G-x)$ allows lower or upper bounds of the form $a \cdot μ_d(G)+b$ with a positive constant $a$. Along the way, the realizability of the four visibility invariants in terms of the order is also characterized in the paper. |
| title | Visibility in graphs under edge and vertex removal |
| topic | Combinatorics 05C12, 05C31, 05C69 |
| url | https://arxiv.org/abs/2505.19340 |