On geodetic sets formed by boundary vertices Original Research Article

Let G be a finite simple connected graph. A vertex image is a boundary vertex of G if there exists a vertex u such that no neighbor of image is further away from u than image. We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices. Before showing that one of the main results in [G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25–34] does not hold for one of the cases, we establish a realization theorem that not only corrects the mentioned wrong statement but also improves it. Given image, its geodetic closure image is the set of all vertices lying on some shortest path joining two vertices of S. We prove that the boundary vertex set image of any graph G is geodetic, that is, image. A vertex image belongs to the contour image of G if no neighbor of image has an eccentricity greater than image. We present some sufficient conditions to guarantee the geodeticity of either the contour image or its geodetic closure image.