2024/05/20 by Pakanun Dokyeesun, Dokyeesun, Pakanun, Sandi Klavžar +3 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2405.11918
openalex publication_date 2024/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \rm gp(G) be the general position number of a graph G. It is proved that \rm gp(G-x)≤ 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 ≤ \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) ≤ \rm gp(G), and that \rm gp(G-x) ≥ \rm gp(G) - 1 when the diameter of G-x remains 2. It is demonstrated that \rm gp(G)/2≤ \rm gp(G-e)≤ 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≤ \rm gp(G-e)≤ \rm gp(G) + 1. All these bounds are proved to be sharp.