**Journal of Prime Research in Mathematics**

Vol. 1 (2009), Issue 1, pp. 149 – 170

ISSN: 1817-3462 (Online) 1818-5495 (Print)

ISSN: 1817-3462 (Online) 1818-5495 (Print)

# On the connected detour number of a graph

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

**Research Department of Mathematics, St. Xavier’s College (Autonomous), Palayamkottai, India.**

S. Athisayanathan

S. Athisayanathan

**
**\(^{1}\)Corresponding Author: apskumar1953@yahoo.co.in

Copyright © 2009 A. P. Santhakumaran, S. Athisayanathan. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

**Published:**December, 2009.

### 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.