Edge Detour Graphs

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 an $edgedetourset$ if every edge in $G$ lies on a detour joining a pair of vertices of $S$. The $edgedetournumber$ $d{n}_1(G)$ of $G$ is the minimum order of its edge detour sets, and any edge detour set of order $d{n}_1(G)$ is an $edgedetourbasis$ of $G$. A connected graph $G$ is called an $edgedetourgraph$ if it has an edge detour set. Certain general properties of these concepts are studied. The edge detour numbers of certain classes of graphs are determined. We show that for each pair of integers $k$ and $p$ with $2\le k<p$, there is an edge detour graph $G$ of order $p$ with $d{n}_1(G)=k$. An edge detour set $S$, no proper subset of which is an edge detour set, is a $minimaledgedetourset$. The $upperedgedetournumber$ $d{n}_1^{+}(G)$ of a graph $G$ is the maximum cardinality of a minimal edge detour set of $G$. We determine the upper edge detour numbers of certain classes of graphs. We also show that for every pair $a,b$ of integers with $2\le a\le 6$, there is an edge detour graph $G$ with $d{n}_1(G)=a$ and $d{n}_1^{+}(G)=b$.