The Connected Detour Number of a Graph

Abstract

For two vertices $u$ and $v$ in a graph $G=(V,E)$, the \emph{detour distance} $D(u,v)$ is the length of a longest $u$-$v$ path in $G$. A $u$-$v$ path of length $D(u,v)$ is called a $u$-$v$ detour. A set $S\subseteq V$ is called a \emph{detour set} of $G$ if every vertex in $G$ lies on a detour joining a pair of vertices of $S$. The \emph{detour number} $dn(G)$ of $G$ is the minimum order of its detour sets, and any detour set of order $dn(G)$ is a detour basis of $G$. A set $S\subseteq V$ is called a \emph{connected detour set} of $G$ if $S$ is a detour set of $G$ and the subgraph $G[S]$ induced by $S$ is connected. The \emph{connected detour number} $cdn(G)$ of $G$ is the minimum order of its connected detour sets, and any connected detour set of order $cdn(G)$ is called a \emph{connected detour basis} of $G$. Certain general properties of these concepts are studied. The connected detour numbers of certain classes of graphs are determined. The relationship of the connected detour number with the detour diameter is discussed, and it is proved that for each triple $D,k,p$ of integers with $3\le k\le p-D-1$ and $D\ge 4$, there is a connected graph $G$ of order $p$ with detour diameter $D$ and $cdn(G)=k$. A connected detour set $S$, no proper subset of which is a connected detour set, is a \emph{minimal connected detour set}. The \emph{upper connected detour number} $cd{n}^{+}(G)$ of a graph $G$ is the maximum cardinality of a minimal connected detour set of $G$. It is shown that for every pair $a,b$ of integers with $5\le a\le b$, there is a connected graph $G$ with $cdn(G)=a$ and $cd{n}^{+}(G)=b$.