|
Algebra and Discrete Mathematics, 2012, Volume 13, Issue 1, Pages 128–138
(Mi adm70)
|
|
|
|
RESEARCH ARTICLE
The upper edge-to-vertex detour number of a graph
A. P. Santhakumaran, S. Athisayanathan Department of Mathematics, St. Xavier's College (Autonomous), Palayamkottai - 627 002, India
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. For subsets A and B of V, the detour distance D(A,B) is defined as D(A,B)=min{D(x,y):x∈A, y∈B}. A u–v path of length D(A,B) is called an A–B detour joining the sets A, B⊆V where u∈A and v∈B. A vertex x is said to lie on an A–B detour if x is a vertex of an A–B detour. A set S⊆E is called an edge-to-vertex detour set if every vertex of G is incident with an edge of S or lies on a detour joining a pair of edges of S. The edge-to-vertex detour number dn2(G) of G is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order dn2(G) is an edge-to-vertex detour basis of G. An edge-to-vertex detour set S in a connected graph G is called a minimal edge-to-vertex detour set of G if no proper subset of S is an edge-to-vertex detour set of G. The upper edge-to-vertex detour number dn+2(G) of G is the maximum cardinality of a minimal edge-to-vertex detour set of G. The upper edge-to-vertex detour numbers of certain standard graphs are obtained. It is shown that for every pair a, b of integers with 2⩽a⩽b, there exists a connected graph G with dn2(G)=a and dn+2(G)=b.
Keywords:
Detour, edge-to-vertex detour set, edge-to-vertex detour basis, edge-to-vertex detour number, upper edge-to-vertex detour number.
Received: 23.11.2011 Revised: 30.11.2011
Citation:
A. P. Santhakumaran, S. Athisayanathan, “The upper edge-to-vertex detour number of a graph”, Algebra Discrete Math., 13:1 (2012), 128–138
Linking options:
https://www.mathnet.ru/eng/adm70 https://www.mathnet.ru/eng/adm/v13/i1/p128
|
Statistics & downloads: |
Abstract page: | 266 | Full-text PDF : | 113 | References: | 68 | First page: | 1 |
|