Eccentricity function in distance-hereditary graphs

Abstract

A graph $G=(V,E)$ is distance hereditary if every induced path of $G$ is a shortest path. In this paper, we show that the eccentricity function $e(v)=\max \{d(v,u):u\in V\}$ in any distance-hereditary graph $G$ is almost unimodal, that is, every vertex $v$ with $e(v)>rad(G)+1$ has a neighbor with smaller eccentricity. Here, $rad(G)=\min \{e(v):v\in V\}$ is the radius of graph $G$. Moreover, we use this result to fully characterize the centers of distance-hereditary graphs. Several bounds on the eccentricity of a vertex with respect to its distance to the center of $G$ or to the ends of a diametral path are established. Finally, we propose a new linear time algorithm to compute all eccentricities in a distance-hereditary graph.

20 pages, 7 figures