The upper edge-to-vertex detour number of a graph

Abstract

For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the 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. For subsets \(A\) and \(B\) of \(V\), the detour distance \(D(A, B)\) is defined as \(D(A, B) = \min\{D(x, y): x \in  A\), \(y \in  B\}\). A \(u\)-\(v\) path of length \(D(A, B)\) is called an \(A\)-\(B\) detour joining the sets \(A\), \(B \subseteq  V\) where \(u\in A\) and \(v \in B\). A vertex \(x\) is said to lie on an \(A\)-\(B\) detour  if \(x\) is a vertex of  an \(A\)-\(B\) detour. A set \(S\subseteq E\) is called an edge-to-vertex   detour  set if every vertex of \(G\) is incident with an edge of \(S\) or lies on a detour joining a pair of edges of \(S\). The edge-to-vertex  detour  number \({dn}_{2}(G)\) of \(G\) is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order \({dn}_{2}(G)\) is an edge-to-vertex  detour basis of \(G\). An edge-to-vertex detour set \(S\) in a connected graph \(G\) is called a minimal edge-to-vertex  detour  set of \(G\) if no proper subset of \(S\) is an edge-to-vertex detour set of \(G\). The upper edge-to-vertex  detour  number, \({dn}_{2}^{+} (G)\) of \(G\) is the maximum cardinality of a minimal edge-to-vertex detour set of \(G\). The upper edge-to-vertex detour numbers of certain standard graphs are obtained. It is shown that for every pair \(a\), \(b\) of integers with \(2 \le a \le b\), there exists a connected graph \(G\) with \(dn_{2}(G)=a\) and \(dn_{2}^{+}(G)=b\).