Detour Graphs

Abstract

Let $G=(V,E)$ be a connected simple graph. Let $u,v\in V(G)$. The detour distance, $D(u,v)$, between $u$ and $v$ is the distance of a longest path from $u$ to $v$. E. Sampathkumar defined the detour graph of $G$, denoted by $D(G)$, as follows: $D(G)$ is an edge-labelled complete graph on $n$ vertices, where $n=|V(G)|$, the edge label for $uv$, $u,v\in V(K_n)$, being $D(u,v)$. Any edge-labelled complete graph need not be the detour graph of a graph. In this paper, we characterize detour graphs of a tree. We also characterize graphs for which the detour distance sequences are given.