Detour Antipodal Graphs

Abstract

For two vertices $u$ and $v$ in a connected graph $G$, the detour distance $D(u,v)$ between $u$ and $v$ is the length of a longest $u–v$ path in $G$. The detour diameter ${\text{diam}}_D(G)$ of $G$ is the greatest detour distance between two vertices of $G$. Two vertices $u$ and $v$ are detour antipodal in $G$ if $D(u,v)={\text{diam}}_D(G)$. The detour antipodal graph $\text{DA}(G)$ of a connected graph $G$ has the same vertex set as $G$ and two vertices $u$ and $v$ are adjacent in $\text{DA}(G)$ if $u$ and $v$ are detour antipodal vertices of $G$. For a connected graph $G$ and a nonnegative integer $r$, define ${\text{DA}}^r(G)$ as $G$ if $r=0$ and as the detour antipodal graph of ${\text{DA}}^{r-1}(G)$ if $r>0$ and ${\text{DA}}^{r-1}(G)$ is connected. Then $\{{\text{DA}}^r(G)\}$ is the detour antipodal sequence of $G$. A graph $H$ is the limit of $\{{\text{DA}}^r(G)\}$ if there exists a positive integer $N$ such that ${\text{DA}}^r(G)\cong H$ for all $r\ge N$. It is shown that $\{{\text{DA}}^r(G)\}$ converges if $G$ is Hamiltonian. All graphs that are the limit of the detour antipodal sequence of some Hamiltonian graph are determined.