Weak Edge 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. A set \(S \subseteq V\) is called a weak edge detour set if every edge in \(G\) has both its ends in \(S\) or it lies on a detour joining a pair of vertices of \(S\). The weak edge detour number \(dn_w(G)\) of \(G\) is the minimum order of its weak edge detour sets and any weak edge detour set of order \(dn_w(G)\) is a weak edge detour basis of \(G\). Certain general properties of these concepts are studied. The weak edge detour numbers of certain classes of graphs are determined. Its relationship with the detour diameter is discussed and it is proved that for each triple \(D, k, p\) of integers with \(8 \leq k \leq p-D+1\) and \(D \geq 3\) there is a connected graph \(G\) of order \(p\) with detour diameter \(D\) and \(dn_w(G) = k\). It is also proved that for any three positive integers \(a, b, k\) with \(k \geq 3\) and \(a \leq b \leq 2a\), there is a connected graph \(G\) with detour radius \(a\), detour diameter \(b\) and \(dn_w(G) = k\). Graphs \(G\) with detour diameter \(D \leq 4\) are characterized for \(dn_w(G) = p-1\) and \(dn_w^+(G) = p-2\) and trees with these numbers are characterized. A weak edge detour set \(S\), no proper subset of which is a weak edge detour set, is a minimal weak edge detour set. The upper weak edge detour number \(dn_w^+(G)\) of a graph \(G\) is the maximum cardinality of a minimal weak edge detour set of \(G\). It is shown that for every pair \(a, b\) of integers with \(2 \leq a \leq b\), there is a connected graph \(G\) with \(dn_w(G) = a\) and \(dn_w^+(G) = b\).