On edge detour graphs

A.P. Santhakumaran; S. Athisayanathan

Discussiones Mathematicae Graph Theory (2010)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.