On Boundary Vertices in Graphs

Abstract

A vertex $v$ of a connected graph $G$ is an eccentric vertex of a vertex $u$ if $v$ is a vertex at greatest distance from $u$; while $v$ is an eccentric vertex of $G$ if $v$ is an eccentric vertex of some vertex of $G$. The subgraph of $G$ induced by its eccentric vertices is the eccentric subgraph of $G$.

A vertex $v$ of $G$ is a boundary vertex of a vertex $u$ if $d(u,w)\le d(u,v)$ for each neighbor $w$ of $v$. A vertex $v$ is a boundary vertex of $G$ if $v$ is a boundary vertex of some vertex of $G$. The subgraph of $G$ induced by its boundary vertices is the boundary of $G$. A vertex $v$ is an interior vertex of $G$ if for every vertex $u$ distinct from $v$, there exists a vertex $w$ distinct from $v$ such that $d(u,w)=d(u,v)+d(v,w)$. The interior of $G$ is the subgraph of $G$ induced by its interior vertices. A vertex $v$ is a boundary vertex of a connected graph if and only if $v$ is not an interior vertex. For every graph $G$, there exists a connected graph $H$ such that $G$ is both the center and interior of $H$.

Relationships between the boundary and the periphery, center, and eccentric subgraph of a graph are studied. The boundary degree of a vertex $v$ in a connected graph $G$ is the number of vertices $u$ in $G$ having $v$ as a boundary vertex. We study, for each pair $r,n$ of integers with $r\ge 0$ and $n\ge 3$, the existence of a connected graph $G$ of order $n$ such that every vertex of $G$ has boundary degree $r$. We also study the boundary vertices of a connected graph from different points of view.