Mutually Eccentric Vertices in Graphs

Abstract

The distance $d(u,v)$ between a pair of vertices $u$ and $v$ is the length of a shortest path joining $u$ and $v$. The eccentricity $e(v)$ of vertex $v$ is the distance to a vertex farthest from $v$. In a graph $G$, an eccentric vertex of $v$ is a vertex farthest from $v$, that is, a vertex $u$ for which $d(u,v)=e(v)$. Given a set $X$ of vertices in $G$, the vertices of $X$ are mutually eccentric provided that for any pair of vertices $u$ and $v$ in $X$, $u$ is an eccentric vertex of $v$ and $v$ is an eccentric vertex of $u$. In this paper, we discuss problems concerning sets of mutually eccentric vertices in graphs.