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.