The Upper Connected Vertex Detour Number of a Graph


A. P. Santhakumaran, P. Titus




For vertices $x$ and $y$ in a connected graph $G=(V,E)$ of order at least two, the detour distance $D(x,y)$ is the length of the longest $x-y$ path in $G$. An $x-y$ path of length $D(x,y)$ is called an $x-y$ detour. For any vertex $x$ in $G$, a set $S\subseteq V$ is an $x$-detour set of $G$ if each vertex $v\in V$ lies on an $x-y$ detour for some element $y$ in $S$. The minimum cardinality of an $x$-detour set of $G$ is defined as the $x$-detour number of $G$, denoted by $d_x(G)$. An $x$-detour set of cardinality $d_x(G)$ is called a $d_x$-set of $G$. A connected $x$-detour set of $G$ is an $x$-detour set $S$ such that the subgraph $G[S]$ induced by $S$ is connected. The minimum cardinality of a connected $x$-detour set of $G$ is the connected $x$-detour number of $G$ and is denoted by $cd_x(G)$. A connected $x$-detour set of cardinality $cd_x(G)$ is called a $cd_x$-set of $G$. A connected $x$-detour set $S_x$ is called a minimal connected $x$-detour set if no proper subset of $S_x$ is a connected $x$-detour set. The upper connected $x$-detour number, denoted by $cd^+_x (G)$, is defined as the maximum cardinality of a minimal connected $x$-detour set of $G$. We determine bounds for $cd^+_x(G)$ and find the same for some special classes of graphs. For any three integers $a$, $b$ and $c$ with $2\leq a<b\leq c$, there is a connected graph $G$ with $d_x(G)=a$, $cd_x(G)=b$ and $cd^+_x(G)=c$ for some vertex $x$ in $G$. It is shown that for positive integers $R,D$ and $n\geq 3$ with $R<D\leq2R$, there exists a connected graph $G$ with detour radius $R$, detour diameter $D$ and $cd^+_x(G)=n$ for some vertex $x$ in $G$.