Detour Distance in Graphs

Abstract

For two vertices $u$ and $v$ in a connected graph $G$, the detour distance $D(u,v)$ from $u$ to $v$ is defined as the length of a longest $u-v$ path in $G$. The detour eccentricity $e_D(v)$ of a vertex $v$ in $G$ is the maximum detour distance from $v$ to a vertex of $G$. The detour radius ${\text{rad}}_D(G)$ of $G$ is the minimum detour eccentricity among the vertices of $G$, while the detour diameter ${\text{diam}}_D(G)$ of $G$ is the maximum detour eccentricity among the vertices of $G$. It is shown that ${\text{rad}}_D(G)<{\text{diam}}_D(G)<2{\text{rad}}_D(G)$ for every connected graph $G$ and that every pair $a,b$ of positive integers with $a\le b\le 2a$ is realizable as the detour radius and detour diameter of some connected graph. The detour center of $G$ is the subgraph induced by those vertices of $G$ having detour eccentricity ${\text{rad}}_D(G)$. A connected graph $G$ is detour self-centered if $G$ is its own detour center. The detour periphery of $G$ is the subgraph induced by the vertices of $G$ having detour eccentricity ${\text{diam}}_D(G)$. It is shown that every graph is the detour center of some connected graph. Detour self-centered graphs are investigated. We present sufficient conditions for a graph to be the detour periphery of some connected graph. Several classes of graphs that are not the detour periphery of any connected graph are determined.