Some Structural, Metric and Convex Properties of the Boundary of a Graph

Abstract

Let \(u,v\) be two vertices of a connected graph \(G\). The vertex \(v\) is said to be a boundary vertex of \(u\) if no neighbor of \(v\) is further away from \(u\) than \(v\). The boundary of a graph is the set of all its boundary vertices.In this work, we present a number of properties of the boundary of a graph under different points of view:(1) A realization theorem involving different types of boundary vertex sets: extreme set, periphery, contour, and the whole boundary.(2) The contour is a monophonic set.(3) The cardinality of the boundary is an upper bound for both the metric dimension and the determining number of a graph.