The Connected Detour Number of a Graph

Abstract

For two vertices $u$ and $v$ in a graph $G=(V,E)$, the $detourdistance$ $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 $detourset$ of $G$ if every vertex in $G$ lies on a detour joining a pair of vertices of $S$. The $detournumber$ $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 $connecteddetourset$ of $G$ if $S$ is a detour set of $G$ and the subgraph $G[S]$ induced by $S$ is connected. The $connecteddetournumber$ $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 $connecteddetourbasis$ 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 $minimalconnecteddetourset$. The $upperconnecteddetournumber$ $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$.