JPRM-Vol. 1 (2010), Issue 1, pp. 13 – 21
Open Access Full-Text PDF
A. P. Santhakumaran, S. Athisayanathan
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 an edge detour set if every edge in \(G\) lies on a detour joining a pair of vertices of \(S\). The edge detour number \(dn_1(G)\) of G is the minimum order of its edge detour sets and any edge detour set of order \(dn_1(G)\) is an edge detour basis of \(G\). A connected graph \(G\) is called an edge detour graph if it has an edge detour set. A subset \(T\) of an edge detour basis \(S\) of an edge detour graph \(G\) is called a forcing subset for \(S\) if \(S\) is the unique edge detour basis containing \(T\). A forcing subset for \(S\) of minimum cardinality is a minimum forcing subset of \(S\). The forcing edge detour number \(fdn_1(S)\) of \(S\), is the minimum cardinality of a forcing subset for \(S\). The forcing edge detour number \(fdn_1(G)\) of \(G\), is \(min{fdn_1(S)}\), where the minimum is taken over all edge detour bases \(S\) in \(G\). 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 \(dn_1(G)\) and \(fdn_1(G)\) satisfy the relation \(0 ≤ fdn_1(G) ≤ dn_1(G)\) and it is proved that for each pair \(a\), \(b\) of integers with \(0 ≤ a ≤ b\) and \(b ≥ 2\), there is an edge detour graph \(G\) with \(fdn_1(G) = a\) and \(dn_1(G) = b\).