Forcing edge detour number of an edge detour graph

Abstract

For two vertices uu and vv in a graph G=(V,E)G=(V,E), the detour distance D(u,v)D(u,v) is the length of a longest u–vu–v path in GG. A u–vu–v path of length D(u,v)D(u,v) is called a u–vu–v detour. A set S⊆VS⊆V is called an edge detour set if every edge in GG lies on a detour joining a pair of vertices of SS. The edge detour number dn1(G)dn1(G) of G is the minimum order of its edge detour sets and any edge detour set of order dn1(G)dn1(G) is an edge detour basis of GG. A connected graph GG is called an edge detour graph if it has an edge detour set. A subset TT of an edge detour basis SS of an edge detour graph GG is called a forcing subset for SS if SS is the unique edge detour basis containing TT. A forcing subset for SS of minimum cardinality is a minimum forcing subset of SS. The forcing edge detour number fdn1(S)fdn1(S) of SS, is the minimum cardinality of a forcing subset for SS. The forcing edge detour number fdn1(G)fdn1(G) of GG, is minfdn1(S)minfdn1(S), where the minimum is taken over all edge detour bases SS in GG. The general properties satisfied by these forcing subsets are discussed and the forcing edge detour numbers of certain classes of standard edge detour graphs are determined. The parameters dn1(G)dn1(G) and fdn1(G)fdn1(G) satisfy the relation 0≤fdn1(G)≤dn1(G)0≤fdn1(G)≤dn1(G) and it is proved that for each pair aa, bb of integers with 0≤a≤b0≤a≤b and b≥2b≥2, there is an edge detour graph GG with fdn1(G)=afdn1(G)=a and dn1(G)=bdn1(G)=b.