The general position number under vertex and edge removal
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915661542850560 |
|---|---|
| author | Dokyeesun, Pakanun Klavžar, Sandi Tian, Jing |
| author_facet | Dokyeesun, Pakanun Klavžar, Sandi Tian, Jing |
| contents | Let ${\rm gp}(G)$ be the general position number of a graph $G$. It is proved that ${\rm gp}(G-x)\leq 2{\rm gp}(G)$ holds for any vertex $x$ of a connected graph $G$ and that if $x$ lies in some ${\rm gp}$-set of $G$, then ${\rm gp}(G) - 1 \le {\rm gp}(G-x)$. Constructions are given which show that ${\rm gp}(G-x)$ can be much larger than ${\rm gp}(G)$ also when $G-x$ is connected. For diameter $2$ graphs it is proved that ${\rm gp}(G-x) \le {\rm gp}(G)$, and that ${\rm gp}(G-x) \ge {\rm gp}(G) - 1$ when the diameter of $G-x$ remains $2$. It is demonstrated that ${\rm gp}(G)/2\le {\rm gp}(G-e)\leq 2{\rm gp}(G)$ holds for any edge $e$ of a graph $G$. For diameter $2$ graphs these results can be improved to ${\rm gp}(G)-1\le {\rm gp}(G-e)\leq\ {\rm gp}(G) + 1$. All these bounds are proved to be sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11918 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The general position number under vertex and edge removal Dokyeesun, Pakanun Klavžar, Sandi Tian, Jing Combinatorics Let ${\rm gp}(G)$ be the general position number of a graph $G$. It is proved that ${\rm gp}(G-x)\leq 2{\rm gp}(G)$ holds for any vertex $x$ of a connected graph $G$ and that if $x$ lies in some ${\rm gp}$-set of $G$, then ${\rm gp}(G) - 1 \le {\rm gp}(G-x)$. Constructions are given which show that ${\rm gp}(G-x)$ can be much larger than ${\rm gp}(G)$ also when $G-x$ is connected. For diameter $2$ graphs it is proved that ${\rm gp}(G-x) \le {\rm gp}(G)$, and that ${\rm gp}(G-x) \ge {\rm gp}(G) - 1$ when the diameter of $G-x$ remains $2$. It is demonstrated that ${\rm gp}(G)/2\le {\rm gp}(G-e)\leq 2{\rm gp}(G)$ holds for any edge $e$ of a graph $G$. For diameter $2$ graphs these results can be improved to ${\rm gp}(G)-1\le {\rm gp}(G-e)\leq\ {\rm gp}(G) + 1$. All these bounds are proved to be sharp. |
| title | The general position number under vertex and edge removal |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.11918 |