# On edge detour graphs

A.P. Santhakumaran; S. Athisayanathan

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 1, page 155-174
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topA.P. Santhakumaran, and S. Athisayanathan. "On edge detour graphs." Discussiones Mathematicae Graph Theory 30.1 (2010): 155-174. <http://eudml.org/doc/271079>.

@article{A2010,

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₁(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.},

author = {A.P. Santhakumaran, S. Athisayanathan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {detour; edge detour set; edge detour basis; edge detour number},

language = {eng},

number = {1},

pages = {155-174},

title = {On edge detour graphs},

url = {http://eudml.org/doc/271079},

volume = {30},

year = {2010},

}

TY - JOUR

AU - A.P. Santhakumaran

AU - S. Athisayanathan

TI - On edge detour graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 1

SP - 155

EP - 174

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

LA - eng

KW - detour; edge detour set; edge detour basis; edge detour number

UR - http://eudml.org/doc/271079

ER -

## References

top- [1] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Reading MA, 1990). Zbl0688.05017
- [2] G. Chartrand, H. Escuadro and P. Zang, Detour distance in graphs, J. Combin. Math. Combin. Comput. 53 (2005) 75-94. Zbl1074.05029
- [3] G. Chartrand, G.L. Johns, and P. Zang, Detour number of a graph, Util. Math. 64 (2003) 97-113. Zbl1033.05032
- [4] G. Chartrand and P. Zang, Distance in graphs-taking the long view, AKCE J. Graphs. Combin. 1 (2004) 1-13. Zbl1062.05051
- [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. Zbl1249.05102
- [7] A.P. Santhakumaran and S. Athisayanathan, Edge detour graphs, J. Combin. Math. Combin. Comput. 69 (2009) 191-204. Zbl1200.05071