The upper edge-to-vertex detour number of a graph
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(...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2012
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/152187 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | The upper edge-to-vertex detour number of a graph / A.P. Santhakumaran, S. Athisayanathan // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 128–138. — Бібліогр.: 9 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859750527372361728 |
|---|---|
| author | Santhakumaran, A.P. Athisayanathan, S. |
| author_facet | Santhakumaran, A.P. Athisayanathan, S. |
| citation_txt | The upper edge-to-vertex detour number of a graph / A.P. Santhakumaran, S. Athisayanathan // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 128–138. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | 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 dn₂(G) of G is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order dn₂(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₂⁺(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₂⁺(G) = b.
|
| first_indexed | 2025-12-01T23:50:33Z |
| format | Article |
| fulltext |
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 13 (2012). Number 1. pp. 128 – 138
c© Journal “Algebra and Discrete Mathematics”
The upper edge-to-vertex detour number
of a graph
A. P. Santhakumaran and S. Athisayanathan
Communicated by D. Simson
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.
2000 Mathematics Subject Classification: 05C12.
Key words and phrases: Detour, edge-to-vertex detour set, edge-to-vertex detour
basis, edge-to-vertex detour number, upper edge-to-vertex detour number.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A. P. Santhakumaran, S. Athisayanathan 129
1. Introduction
By a graph G = (V,E) we mean a finite undirected graph without
loops or multiple edges. The order and size of G are denoted by p and q
respectively. We consider connected graphs with at least two vertices. For
basic definitions and terminologies we refer to [1, 5]. For vertices u and v
in a connected graph G, the distance d(u, v) is the length of a shortest
u–v path in G. A u–v path of length d(u, v) is called a u–v geodesic. For a
vertex v of G, the eccentricity e(v) is the distance between v and a vertex
farthest from v. The minimum eccentricity among the vertices of G is
the radius, rad G and the maximum eccentricity is its diameter, diam G
of G. For vertices u and v in a connected graph G, 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. The detour eccentricity eD(v) of a vertex v
in G is the maximum detour distance from v to a vertex of G. The detour
radius, radDG of G is the minimum detour eccentricity among the vertices
of G, while the detour diameter, diamDG of G is the maximum detour
eccentricity among the vertices of G. It is known that the distance and
the detour distance are metrics on the vertex set V . The detour distance
was studied by Chartrand et al. in [2,4]. A vertex x is said to lie on a u–v
detour P if x is a vertex of P including the vertices u and v. A set S ⊆ V
is called a detour set if every vertex v in G lies on a detour joining a pair
of vertices of S. The detour number dn(G) of G is the minimum order of
a detour set and any detour set of order dn(G) is called a detour basis of
G. A vertex v that belongs to every detour basis of G is a detour vertex
in G. If G has a unique detour basis S, then every vertex in S is a detour
vertex in G. These concepts were studied by Chartrand et al. [3]. The
detour concepts and colorings are widely used in the Channel Assignment
problem in radio technologies [4]. The connected detour number of a
graph was introduced and studied in [8].
In general, there are graphs G for which there exist edges which do
not lie on a detour joining any pair of vertices of V . For the graph G
given in Figure 1.1, the edge v1v2 does not lie on a detour joining any
pair of vertices of V . This motivated us to introduce the concepts of weak
edge detour set of a graph and also edge detour graphs and were studied
in [6, 7].
Definition 1.1 ([6]). Let G = (V,E) be a connected graph with at least
two vertices. A set S ⊆ V is called a weak edge detour set of G if every
edge in G has both its ends in S or it lies on a detour joining a pair of
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
130 The upper edge-to-vertex detour number of a graph
b b
b
b
b
b
b
b
v1 v2
Figure 1.1: G
vertices of S. The weak edge detour number dnw(G) of G is the minimum
order of its weak edge detour sets and any weak edge detour set of order
dnw(G) is called a weak edge detour basis of G.
Example 1.2. For the graph G given in Figure 1.1, it is clear that the
set S = {v1, v2} is a weak edge detour basis of G so that dnw(G) = 2. For
the graph G given in Figure 1.2, it is clear that no two element subset
of V is a weak edge detour set of G. The set S = {v1, v2, v3} is a weak
edge detour basis of G so that dnw(G) = 3. The set S1 = {v1, v4, v5} is
another weak edge detour basis of G.
b
b
b
b
bb
bb
v4 v5
v2
v1
v3
Figure 1.2: G
Definition 1.3 ([7]). Let G = (V,E) be a connected graph with atleast
two vertices. A set S ⊆ V is called an edge detour set of G 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 called an edge detour basis of G. A graph G
is called an edge detour graph if it has an edge detour set.
Example 1.4. For the graph G given in Figure 1.2, it is clear that no two
element subset of V is an edge detour set of G. The set S = {v1, v4, v5} is
a an edge detour basis of G so that dn1(G) = 3 and hence it is an edge
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A. P. Santhakumaran, S. Athisayanathan 131
detour graph. But the graph G given in Figure 1.1 is not an edge detour
graph.
The edge-to-vertex detour number of a graph was introduced and
studied in [9].
Definition 1.5. [9] Let G = (V,E) be a connected graph with at least
three vertices. 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 and B, 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. For A = {u, v} and B = {z, w} with uv and zw edges,
we write an A–B detour as uv– zw detour and D(A,B) as D(uv, zw).
Example 1.6. For the graph G given in Figure 1.3, with A = {v1, v2}
and B = {v4, v5, v6}, v1, v2, v3, v4 and v1, v6, v5, v4 are the v1– v4 detours,
v1, v2, v3, v4, v6, v5 is the v1– v5 detour, v1, v2, v3, v4, v5,v6 is the v1– v6
detour, v2, v1, v6, v5, v4 is the v2– v4 detour, v2, v1, v6, v4, v5 and v2, v3,
v4, v6, v5 are the v2– v5 detours and v2, v3, v4, v5, v6 is the v2– v6 detour.
Hence D(A,B) = 3 and an A–B detour is a v1– v4 detour so that v1, v2,
v3, v4 and v1, v6, v5, v4 are the only two A–B detours.
b
b
b
b
bb
bb b
b
bv1 v2
v6
v5
v4
v3
Figure 1.3: G
Definition 1.7. [9] Let G = (V,E) be a connected graph with at least
three vertices. A set S ⊆ E is called an edge-to-vertex detour set of G
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 cardinality of its edge-to-vertex detour sets and any
edge-to-vertex detour set of cardinality dn2(G) is an edge-to-vertex detour
basis of G.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
132 The upper edge-to-vertex detour number of a graph
Example 1.8. For the graph G given in Figure 1.4, the two v1v2– v4v5
detours are P : v2, v1, v6, v5 and Q : v2, v3, v4, v5, each of length 3 so that
D(v1v2, v4v5) = 3. Since the vertices v6 and v3 lie on the v1v2– v4v5 detours
P and Q respectively, S1 = {v1v2, v4v5} is an edge-to-vertex detour basis
of G so that dn2(G) = 2. Also S2 = {v1v6, v3v4} is another edge-to-vertex
detour basis of G. Thus there can be more than one edge-to-vertex detour
basis for a graph.
b
b b
b
bb
b
b
b
b
b
v1
v2 v3
v6 v5
v4
Figure 1.4: G
Throughout this paper G denotes a connected graph with at least
three vertices. We need the following theorems in the sequel.
Theorem 1.9. [9] Every end-edge of a connected graph G belongs to every
edge-to-vertex detour set of G. Also if the set S of all end-edges of G is
an edge-to-vertex detour set, then S is the unique edge-to-vertex detour
basis for G.
Theorem 1.10. [9] If T is a tree with k end-edges, then dn2(T ) = k.
2. The upper edge-to-vertex detour number of a graph
Definition 2.1. 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.
Example 2.2. For the graph G given in Figure 2.1, S1 = {uv, xy} and
S2 = {uv, vx, vy}, are the minimal edge-to-vertex detour sets of G so that
dn2(G) = 2 and dn+
2 (G) = 3.
It is clear that every minimum edge-to-vertex detour set is a minimal
edge-to-vertex detour set. However, the converse is not true. For the graph
G given in Figure 2.1, S2 = {uv, vx, vy} is a minimal edge-to-vertex detour
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A. P. Santhakumaran, S. Athisayanathan 133
b
b b
b
b
v
u
x y
Figure 2.1: G
set of G but not a minimum edge-to-vertex detour set of G. Since any
edge-to-vertex detour basis of a graph G is also a minimal edge-to-vertex
detour set of G, we have the following theorem.
Theorem 2.3. For any connected graph G, 2 ≤ dn2(G) ≤ dn+
2 (G).
We observe that the bound in Theorem 2.3 is sharp. For any path Pn(n ≥
3), dn2(Pn) = dn+
2 (Pn) = 2. Also for the graph G given in Figure 2.1,
dn2(G) < dn+
2 (G).
Now, we proceed to determine dn2(G) and dn+
2 (G) for some classes
of graphs.
Theorem 2.4. (i) For the complete graph Kp (p ≥ 4), a set S of edges is
an edge-to-vertex detour basis if and only if S consists of two independent
edges of Kp.
(ii) For the complete bipartite graph Km,n (2 ≤ m ≤ n), a set S of edges is
an edge-to-vertex detour basis if and only if S consists of two independent
edges of Km,n.
Proof. (i) Let S = {e, f} be any set of two independent edges of Kp.
Then it is clear that D(e, f) = p − 1 and hence it follows that S is an
edge-to-vertex detour set of Kp. Now, let S be an edge-to-vertex detour
basis of Kp. Let S ′ be any set consisting of two independent edges. Then
as in the first part of this theorem S ′ is an edge-to-vertex detour basis of
Kp. Hence |S| = |S ′| = 2. Let S = {e, f}. If e and f are not independent,
then D(e, f) = 0 and since p ≥ 4, S can not be an edge-to-vertex detour
set of G, which is a contradiction. Thus S consists of two independent
edges.
(ii) Let X and Y be the bipartite sets of Km,n (2 ≤ m ≤ n) with |X| = m
and |Y | = n and let S = {uv, zw} be a set of any two independent
edges of Km,n such that u, z ∈ X and v, w ∈ Y . We show that S is an
edge-to-vertex detour basis of Km,n.
Case 1: Let m = n = 2. Then Km,n = C4 and it is clear that every vertex
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
134 The upper edge-to-vertex detour number of a graph
of Km,n is incident with an edge of S so that S is an edge-to-vertex detour
basis of Km,n.
Case 2: Let 2 ≤ m ≤ n and n 6= 2. We consider two subcases:
Subcase 1: Let m < n. It is clear that D(u, z) = 2(m − 1), D(u,w) =
D(v, z) = 2m−1, D(v, w) = 2m and so D(uv, zw) = 2(m−1). Let y ∈ Y
be any vertex different from v and w. If m > 2, consider any set of m− 2
vertices y1, y2, . . . , ym−2 from Y – {v, y, w}. Then the vertex y lies on
the uv–wz detour P : u = x1, y, x2, y1, x3, y2, . . . , xm−1, ym−2, xm = z,
where x1, x2, . . . , xm ∈ X. If m = 2, then y lies on the uv–wz detour
Q : u, y, z. Since every vertex of X also lies on the same detour P and Q
in respective cases, it follows that S is an edge-to-vertex detour basis of
Km,n and hence dn2(Km,n) = 2.
Subcase 2: Let m = n. It is clear that D(u, z) = D(v, w) = 2(m − 1),
D(u,w) = D(v, z) = 2m− 1 and so D(uv, zw) = 2(m− 1). Also P : u, v,
x1, y1, x2, y2, . . . , xm−2, ym−2, z, where u, x1, x2, . . . , xm−2, z ∈ X and
v, y1, y2, . . . , ym−2 ∈ Y with w 6= vi (1 ≤ i ≤ m− 2) is a uv– zw detour
containing all vertices of Km,n other than the vertex w. Since w is incident
with the edge zw, it follows that S is an edge-to-vertex detour basis of
Km,n. The proof of the converse is similar to that of Theorem 2.4(i).
Theorem 2.5. For the complete graph Kp (p ≥ 3), a set S of edges is a
minimal edge-to-vertex detour set of Kp if and only if S consists of any
two independent edges or S consists of all edges incident at any vertex
of Kp.
Proof. For p = 3, it is clear that a set S of edges is a minimal edge-to-
vertex detour set of K3 if and only if S consists of all edges that are
incident at a vertex of K3.
Let p ≥ 4. If S consists of any two independent edges of Kp, then by
Theorem 2.4(i), S is an edge-to-vertex detour basis of Kp so that S is
minimal. If S consists of all edges incident at any vertex, say v of Kp,
then since every vertex of Kp is incident with an edge of S, it follows that
S is an edge-to-vertex detour set of Kp. We show that S is a minimal
edge-to-vertex detour set of Kp. If T is a proper subset of S, then there
exists at least one edge, say e = vv1 of S such that e /∈ T . Then it is clear
that the vertex v1 neither lies on any detour joining a pair of edges of T
nor is incident with any edge of Tand so T is not an edge-to-vertex detour
set of Kp. Thus S is a minimal edge-to-vertex detour set of Kp.
Conversely, assume that S is a minimal edge-to-vertex detour set of
Kp (p ≥ 4). If |S| = 2, then S is an edge-to-vertex detour basis of G and
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A. P. Santhakumaran, S. Athisayanathan 135
so by Theorem 2.4(i), it is clear that S contains exactly two independent
edges of Kp. Let |S| = 3. Since S is minimal, it follows from Theorem 2.4(i)
that no two edges of S are independent. Hence it follows that the subgraph
induced by S is either K3 or the star K1,3. If it is K3, then since p ≥ 4,
it follows that S is not an edge-to-vertex detour set of Kp, which is a
contradiction. Hence the subgraph induced by S is K1,3. Since p ≥ 4 and
S is an edge-to-vertex detour set, it follows that the graph is K4 and S
contains all edges incident at any vertex of K4.
Let |S| ≥ 4. We show that the subgraph induced by S can not contain
K3. Suppose that the subgraph induced by S contains K3. Let v1, v2, v3
be the vertices of K3. Since |S| ≥ 4, there is an edge e in S different from
the edges of K3. Since S is minimal, it follows that the edge e is incident
with a vertex, say v1 of K3. Now the edges e and v2v3 are independent
and it follows that S is not minimal, which is a contradiction. Thus the
subgraph induced by S does not contain K3. Since S is an edge-to-vertex
detour set of Kp, it follows that S contains all edges incident at any vertex
of Kp.
Theorem 2.6. For the complete bipartite graph Km,n (2 ≤ m ≤ n), a set
S of edges is a minimal edge-to-vertex detour set of Km,n if and only if S
consists of any two independent edges.
Proof. Let S consist of any two independent edges of Km,n. Then by
Theorem 2.4(ii), S is an edge-to-vertex detour basis of Km,n so that S is
minimal.
Conversely assume that S is a minimal edge-to-vertex detour set of
Km,n. If |S| = 2, then S is an edge-to-vertex detour basis of G and so by
Theorem 2.4(ii), it is clear that S contains exactly two independent edges
of Km,n. Let |S| ≥ 3. Since S is minimal, it follows from Theorem 2.4(ii)
that no two edges of S are independent. Since the graph is a bipartite
graph, the subgraph induced by S can not contain K3. Hence it follows
that the subgraph induced by S is a star at a vertex, say v. Let v belong
to a bipartite set X of Km,n. Since m, n ≥ 2, there exists a vertex u ∈ X
such that u 6= v and it is clear that the vertex u is neither incident with
any edge of S nor lies on a detour joining a pair of edges of S. Hence S is
not an edge-to-vertex detour set of Km,n, which is a contradiction. Thus
S consists of two independent edges.
Theorem 2.7. (i) If G is the complete graph Kp (p ≥ 3), then dn2(G) = 2,
dn+
2 (G) = p− 1.
(ii) If G is the complete bipartite graph Km,n (2 ≤ m ≤ n), then dn2(G) =
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
136 The upper edge-to-vertex detour number of a graph
dn+
2 (G) = 2.
(iii) If G is a tree with k end-vertices, then dn2(G) = dn+
2 (G) = k.
Proof. (i) This follows from Theorem 2.4(i) and Theorem 2.5.
(ii) This follows from Theorem 2.4(ii) and Theorem 2.6.
(iii) This follows from Theorems 1.9 and 1.10.
Problem 2.8. Characterize connected graphs G with dn2(G) = dn+
2 (G).
Theorem 2.9. For any cycle G = Cp of length p ≥ 3, we have dn2(G) = 2.
Proof. For p = 3, the result follows from the Theorem 2.7(i). For p ≥ 4,
let Cp : v1, v2, . . . , vp−1, vp, v1 be the cycle of length p ≥ 4. Let S = {v1v2,
vp−1vp}. Then S is an edge-to-vertex-detour basis of Cp and so dn2(G) =
2.
Problem 2.10. Determine dn+
2 (G) for a cycle G.
In view of Theorem 2.3, the following theorem gives a realization
result.
Theorem 2.11. 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.
Proof. Let a = b. Then by Theorem 2.7(iii), dn2(T ) = dn+
2 (T ) = a for any
tree T with a end-vertices. Let 2 ≤ a < b. Let G be the graph obtained from
the complete graph Kb−a+2 by adding a− 1 new vertices y1, y2, . . . , ya−1
and joining them to a vertex, say v of Kb−a+2. The graph G is connected
and is shown in Figure 2.2. Let v, v1, v2, . . . , vb−a+1 be the vertices of
Kb−a+2, X = {vv1, vv2, . . . , vvb−a+1}, Y = {vy1, vy2, . . . , vya−1} and Z
be the set of edges of Kb−a+2 which are not incident at v.
b
b
b
b
b
b
v
y1
y2
ya−1
b
b
b
Kb−a+2
Figure 2.2: G
First, we show that dn2(G) = a. By Theorem 1.9, every edge-to-vertex
detour set of G contains Y . Clearly Y is not an edge-to-vertex detour set
of G and so dn2(G) ≥ |Y |+ 1 = a. On the other hand, let S = Y ∪ {f},
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A. P. Santhakumaran, S. Athisayanathan 137
where f ∈ Z. Then D(e, f) = b − a + 1 for any e ∈ Y and f ∈ Z and
every vertex of Kb−a+2 lies on a e−f detour. Hence S is an edge-to-vertex
detour set of G and so dn2(G) ≤ |S| = a. Therefore dn2(G) = a.
Now, we show that dn+
2 (G) = b. Let S = X ∪ Y . Then every vertex of
G is incident with an edge of S and so S is an edge-to-vertex detour set of
G. We show that S is a minimal edge-to-vertex detour set of G. Assume,
to the contrary, that S is not a minimal edge-to-vertex detour set of G.
Then there is a proper subset T of S such that T is an edge-to-vertex
detour set of G. Since T is a proper subset of S, there exists an edge e ∈ S
and e /∈ T . By Theorem 1.9, every edge-to-vertex detour set contains all
end-edges of G and so we must have e = vvi for some i (1 ≤ i ≤ b− a+1).
Then it is clear that the vertex vi neither lies on any detour joining a pair
of edges of T nor is incident with any edge of T and so T is not an edge-
to-vertex detour set of G, which is a contradiction. Thus S is a minimal
edge-to-vertex detour set of G and so dn+
2 (G) ≥ |S| = b−a+1+a−1 = b.
Now, if dn+
2 (G) > b, then let M be a minimal edge-to-vertex detour set of
G with |M | > b. Then there exists at least one edge, say e ∈ M such that
e /∈ S = X ∪ Y . By Theorem 1.9, M contains Y and hence e is an edge of
Kb−a+2 such that e 6= vvi (1 ≤ i ≤ b−a+1). Thus e ∈ Z and S ′ = Y ∪{e}
is a proper subset of M . It is clear that S ′ is an edge-to-vertex detour set
of G so that M is not a minimal edge-to-vertex detour set of G, which is
a contradiction. Therefore, dn+
2 (G) = b.
Remark 2.12. The graph G in Figure 2.2 contains exactly (b−a+1)C2+1
minimal edge-to-vertex detour sets namely X ∪ Y and Y ∪ {e}, where
e ∈ Z. Hence this example shows that there is no “Intermediate Value
Theorem” for minimal edge-to-vertex detour sets, that is, if k is an integer
such that dn2(G) < k < dn+
2 (G), then there need not exist a minimal
edge-to-vertex detour set of cardinality k in G.
Using the structure of the graph G constructed in the proof of The-
orem 2.11, we can obtain a graph Hn of order n with dn2(G) = 2 and
dn+
2 (G) = n− 1 for all n ≥ 4. Thus we have the following.
Theorem 2.13. There is an infinite sequence {Hn} of connected graphs
Hn of order n ≥ 4 such that dn2(Hn) = 2, dn+
2 (Hn) = n − 1,
limn→∞
dn2(Hn)
n
= 0 and limn→∞
dn
+
2
(Hn)
n
= 1.
Proof. Let Hn be the graph obtained from the complete graph Kn−1 by
adding a new vertex y and joining it to a vertex, say v of Kn−1. Clearly
the graph Hn is connected and is shown in Figure 2.3.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
138 The upper edge-to-vertex detour number of a graph
bb vy
Kn−1
Figure 2.3: Hn
Let v, v1, v2, . . . , vn−2 be the vertices ofKn−1,X = {vv1, vv2, . . . , vvn−2},
Y = {vy} and Z be the set of edges of Kn−1 which are not incident at
v. It is clear from the proof of Theorem 2.11 that the graph Hn contains
exactly (n− 2)C2 + 1 minimal edge-to-vertex detour sets namely X ∪ Y
and Y ∪ {e}, where e ∈ Z so that dn2(Hn) = 2 and dn+
2 (Hn) = n − 1.
Hence the theorem follows.
References
[1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Reading MA,
(1990).
[2] G. Chartrand, H. Escuadro, and P. Zhang, Detour Distance in Graphs, J. Combin.
Math. Combin. Comput. 53 (2005), 75–94.
[3] G. Chartrand, G.L. Johns, and P. Zhang, 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, No.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.,98 (2011), 33-61.
[7] A. P. Santhakumaran and S. Athisayanathan, Edge Detour Graphs, J. Combin.
Math. Combin. Comput., 69 (2009), 191-204.
[8] A. P. Santhakumaran and S. Athisayanathan, Connected detour number of a graph,
J. Combin. Math. Combin. Comput., 69 (2009), 205-218.
[9] A. P. Santhakumaran and S. Athisayanathan, Edge-to-vertex detour number of a
graph, Adv. Studies Contem. Math., 21 (2011), No. 4, 395-412.
Contact information
A. P.
Santhakumaran,
S. Athisayanathan
Department of Mathematics, St. Xavier’s College
(Autonomous), Palayamkottai - 627 002, India
E-Mail: apskumar1953@yahoo.co.in,
athisayanathan@yahoo.co.in
Received by the editors: 23.11.2011
and in final form 30.11.2011.
A. P. Santhakumaran, S. Athisayanathan
|
| id | nasplib_isofts_kiev_ua-123456789-152187 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-01T23:50:33Z |
| publishDate | 2012 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Santhakumaran, A.P. Athisayanathan, S. 2019-06-08T11:06:34Z 2019-06-08T11:06:34Z 2012 The upper edge-to-vertex detour number of a graph / A.P. Santhakumaran, S. Athisayanathan // Algebra and Discrete Mathematics. — 2012. — Vol. 13, № 1. — С. 128–138. — Бібліогр.: 9 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:05C12. https://nasplib.isofts.kiev.ua/handle/123456789/152187 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 dn₂(G) of G is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order dn₂(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₂⁺(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₂⁺(G) = b. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics The upper edge-to-vertex detour number of a graph Article published earlier |
| spellingShingle | The upper edge-to-vertex detour number of a graph Santhakumaran, A.P. Athisayanathan, S. |
| title | The upper edge-to-vertex detour number of a graph |
| title_full | The upper edge-to-vertex detour number of a graph |
| title_fullStr | The upper edge-to-vertex detour number of a graph |
| title_full_unstemmed | The upper edge-to-vertex detour number of a graph |
| title_short | The upper edge-to-vertex detour number of a graph |
| title_sort | upper edge-to-vertex detour number of a graph |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/152187 |
| work_keys_str_mv | AT santhakumaranap theupperedgetovertexdetournumberofagraph AT athisayanathans theupperedgetovertexdetournumberofagraph AT santhakumaranap upperedgetovertexdetournumberofagraph AT athisayanathans upperedgetovertexdetournumberofagraph |