Geodesic
On edge detour graphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 1, pp. 155-174.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: detour, edge detour set, edge detour basis, edge detour number 
@article{DMGT_2010_30_1_a12,
     author = {Santhakumaran, A.P. and Athisayanathan, S.},
     title = {On edge detour graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {155--174},
     publisher = {mathdoc},
     volume = {30},
     number = {1},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a12/}
}
TY  - JOUR
AU  - Santhakumaran, A.P.
AU  - Athisayanathan, S.
TI  - On edge detour graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 155
EP  - 174
VL  - 30
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a12/
LA  - en
ID  - DMGT_2010_30_1_a12
ER  - 
%0 Journal Article
%A Santhakumaran, A.P.
%A Athisayanathan, S.
%T On edge detour graphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 155-174
%V 30
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a12/
%G en
%F DMGT_2010_30_1_a12
Santhakumaran, A.P.; Athisayanathan, S. On edge detour graphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 1, pp. 155-174. http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a12/

[1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990).

[2] G. Chartrand, H. Escuadro and P. Zang, Detour distance in graphs, J. Combin. Math. Combin. Comput. 53 (2005) 75-94.

[3] G. Chartrand, G.L. Johns, and P. Zang, Detour number of a graph, Util. Math. 64 (2003) 97-113.

[4] G. Chartrand and P. Zang, Distance in graphs-taking the long view, AKCE J. Graphs. Combin. 1 (2004) 1-13.

[5] G. Chartrand and P. Zang, Introduction to Graph Theory (Tata McGraw-Hill, New Delhi, 2006).

[6] A.P. Santhakumaran and S. Athisayanathan, Weak edge detour number of a graph, Ars Combin., to appear.

[7] A.P. Santhakumaran and S. Athisayanathan, Edge detour graphs, J. Combin. Math. Combin. Comput. 69 (2009) 191-204.