On edge detour graphs

Santhakumaran, A.P. ; Athisayanathan, S.

Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 1, pp. 155-174

Résumé

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₁(G) of G is the minimum order of its edge detour sets and any edge detour set of order dn₁(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. It is proved that for any non-trivial tree T of order p and detour diameter D, dn₁(T) ≤ p-D+1 and dn₁(T) = p-D+1 if and only if T is a caterpillar. We show that for each triple D, k, p of integers with 3 ≤ k ≤ p-D+1 and D ≥ 4, there is an edge detour graph G of order p with detour diameter D and dn₁(G) = k. We also show that for any three positive integers R, D, k with k ≥ 3 and R D ≤ 2R, there is an edge detour graph G with detour radius R, detour diameter D and dn₁(G) = k. Edge detour graphs G with detour diameter D ≤ 4 are characterized when dn₁(G) = p-2 or dn₁(G) = p-1.

Détail

Keywords: detour, edge detour set, edge detour basis, edge detour number