On the connected detour number of a graph

Abstract

For two vertices u and v 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 a detour set of GG if every vertex in GG lies on a detour joining a pair of vertices of SS. The detour number dn(G)dn(G) of G is the minimum order of its detour sets and any detour set of order dn(G)dn(G) is a detour basis of GG. A set S⊆VS⊆V is called a connected detour set of GG if S is detour set of GG and the subgraph G[S]G[S] induced by S is connected. The connected detour number cdn(G)cdn(G) of GG is the minimum order of its connected detour sets and any connected detour set of order cdn(G)cdn(G) is called a connected detour basis of GG. Graphs G with detour diameter D≤4D≤4 are characterized when cdn(G)=pcdn(G)=p, cdn(G)=p−1cdn(G)=p−1, cdn(G)=p−2cdn(G)=p−2 or cdn(G)=2cdn(G)=2. A subset TT of a connected detour basis SS of GG is a forcing subset for SS if SS is the unique connected detour basis containing TT. The forcing connected detour number fcdn(S)fcdn(S) of SS is the minimum cardinality of a forcing subset for SS. The forcing connected detour number fcdn(G)fcdn(G) of GG is minfcdn(S)minfcdn(S), where the minimum is taken over all connected detour bases SS in GG. The forcing connected detour numbers of certain classes of graphs are determined. It is also shown that for each pair aa, bb of integers with 0≤a<b0≤a<b and b≥3b≥3, there is a connected graph GG with fcdn(G)=afcdn(G)=a and cdn(G)=bcdn(G)=b.