PDF
Discussiones Mathematicae Graph Theory 30(1) (2010)
155-174
DOI: https://doi.org/10.7151/dmgt.1484
ON EDGE DETOUR GRAPHS
A.P. Santhakumaran and S. Athisayanathan
Research Department of Mathematics
St. Xavier's College (Autonomous)
Palayamkottai - 627 002, India
e-mail: apskumar1953@yahoo.co.in
e-mail: athisayanathan@yahoo.co.in
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 dn1(G) of G is the minimum order of its edge detour sets and any edge detour set of order dn1(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, dn1(T) ≤ p-D+1 and dn1(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 dn1(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 dn1(G) = k. Edge detour graphs G with detour diameter D ≤ 4 are characterized when dn1(G) = p-2 or dn1(G) = p-1.Keywords: detour, edge detour set, edge detour basis, edge detour number.
2010 Mathematics Subject Classification: 05C12.
References
| [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. |
Received 25 January 2009
Revised 28 May 2009
Accepted 28 May 2009
Close