Journal of Prime Research in Mathematics

On the connected detour number of a graph

A. P. Santhakumaran
Research Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai, India.
S. Athisayanathan
Research Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai, India.

$$^{1}$$Corresponding Author: apskumar1953@yahoo.co.in

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

Keywords:

Detour, connected detour set, connected detour basis, connected detour number, forcing connected detour number.