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.