The detour hull number of a graph
For vertices u and v in a connected graph G = (V, E), the set ID[u, v] consists of all those vertices lying on a u−v longest path in G. Given a set S of vertices of G, the union of all sets ID[u, v] for u, v ∈ S, is denoted by ID[S]. A set S is a detour convex set if ID[S] = S. The detour convex hul...
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/152246 |
| 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 detour hull number of a graph / A.P. Santhakumaran, S.V. Ullas Chandran // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 307–322. — Бібліогр.: 14 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859707989206761472 |
|---|---|
| author | Santhakumaran, A.P. Ullas Chandran, S.V. |
| author_facet | Santhakumaran, A.P. Ullas Chandran, S.V. |
| citation_txt | The detour hull number of a graph / A.P. Santhakumaran, S.V. Ullas Chandran // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 307–322. — Бібліогр.: 14 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | For vertices u and v in a connected graph G = (V, E), the set ID[u, v] consists of all those vertices lying on a u−v longest path in G. Given a set S of vertices of G, the union of all sets ID[u, v] for u, v ∈ S, is denoted by ID[S]. A set S is a detour convex set if ID[S] = S. The detour convex hull [S]D of S in G is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among the subsets S of V with [S]D = V. A set S of vertices is called a detour set if ID[S] = V. The minimum cardinality of a detour set is the detour number dn(G) of G. A vertex x in G is a detour extreme vertex if it is an initial or terminal vertex of any detour containing x. Certain general properties of these concepts are studied. It is shown that for each pair of positive integers r and s, there is a connected graph G with r detour extreme vertices, each of degree s. Also, it is proved that every two integers a and b with 2 ≤ a ≤ b are realizable as the detour hull number and the detour number respectively, of some graph. For each triple D, k and n of positive integers with 2 ≤ k ≤ n − D + 1 and D ≥ 2, there is a connected graph of order n, detour diameter D and detour hull number k. Bounds for the detour hull number of a graph are obtained. It is proved that dn(G) = dh(G) for a connected graph G with detour diameter at most 4. Also, it is proved that for positive integers a, b and k ≥ 2 with a < b ≤ 2a, there exists a connected graph G with detour radius a, detour diameter b and detour hull number k. Graphs G for which dh(G) = n − 1 or dh(G) = n − 2 are characterized.
|
| first_indexed | 2025-12-01T04:11:46Z |
| 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 14 (2012). Number 2. pp. 307 – 322
c© Journal “Algebra and Discrete Mathematics”
The detour hull number of a graph1
A.P. Santhakumaran and S.V. Ullas Chandran
Communicated by I. V. Protasov
Abstract. For vertices u and v in a connected graph G =
(V, E), the set ID[u, v] consists of all those vertices lying on a u − v
longest path in G. Given a set S of vertices of G, the union of all
sets ID[u, v] for u, v ∈ S, is denoted by ID[S]. A set S is a detour
convex set if ID[S] = S. The detour convex hull [S]D of S in G
is the smallest detour convex set containing S. The detour hull
number dh(G) is the minimum cardinality among the subsets S
of V with [S]D = V . A set S of vertices is called a detour set if
ID[S] = V . The minimum cardinality of a detour set is the detour
number dn(G) of G. A vertex x in G is a detour extreme vertex
if it is an initial or terminal vertex of any detour containing x.
Certain general properties of these concepts are studied. It is shown
that for each pair of positive integers r and s, there is a connected
graph G with r detour extreme vertices, each of degree s. Also, it is
proved that every two integers a and b with 2 ≤ a ≤ b are realizable
as the detour hull number and the detour number respectively, of
some graph. For each triple D, k and n of positive integers with
2 ≤ k ≤ n − D + 1 and D ≥ 2, there is a connected graph of
order n, detour diameter D and detour hull number k. Bounds for
the detour hull number of a graph are obtained. It is proved that
dn(G) = dh(G) for a connected graph G with detour diameter at
most 4. Also, it is proved that for positive integers a, b and k ≥ 2
with a < b ≤ 2a, there exists a connected graph G with detour
radius a, detour diameter b and detour hull number k. Graphs G
for which dh(G) = n − 1 or dh(G) = n − 2 are characterized.
1Research supported by DST Project No. SR/S4/MS: 319/06
2010 MSC: 05C12.
Key words and phrases: detour, detour convex set, detour number, detour
extreme vertex, detour hull number.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
308 The detour hull number of a graph
1. Introduction
By a graph G = (V, E), we mean a finite undirected connected graph
without loops or multiple edges. The order and size of G are denoted by
n and m respectively. For basic definitions and terminologies, we refer
to [1, 9]. The distance d(u, v) between two vertices u and v in a connected
graph G is the length of a shortest u - v path in G. An u - v path of length
d(u, v) is called an u - v geodesic. The set I[u, v] consists of all vertices
lying on some u - v geodesic of G; while for S ⊆ V , I[S] =
⋃
u,v∈S
I[u, v].
The set S is convex if I[S] = S. The convex hull [S] is the smallest convex
containing S. A set S of vertices of G is a hull set of G if [S] = V . The
hull number h(G) of G is the minimum cardinality of a hull set and any
hull set of cardinality h(G) is called a minimum hull set of G. A set
S of vertices of G is a geodetic set if I[S] = V , and a geodetic set of
minimum cardinality is a minimum geodetic set of G. The cardinality of a
minimum geodetic set of G is the geodetic number g(G). These concepts
were studied in [1, 3, 4, 5, 6, 11]
For vertices u and v in a nontrivial connected graph G, the detour
distance D(u, v) is the length of a longest x − v path in G. An u − v path
of length D(u, v) is an u − v detour. It is known that the detour distance
is a metric on the vertex set V of G. 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, radD(G) of G is the minimum detour eccentricity
among the vertices of G, while the detour diameter, diamD(G) of G is
the maximum detour eccentricity among the vertices of G. The detour
distance of a graph was studied in [2].
The set ID[u, v] consists of all vertices lying on some u−v detour of G;
while for S ⊆ V , ID[S] =
⋃
u,v∈S
ID[u, v]. A set S ⊆ V is called a detour set
if ID[S] = V . The detour number dn(G) of G is the minimum cardinality
of a detour set and any detour set of cardinality dn(G) is called a minimum
detour set of G. The detour number of a graph was introduced in [7] and
further studied in [14]. These concepts have interesting applications in
Channel Assignment Problem in radio technologies [8, 12]. In [13], the
distance martix and the detour matrix of a connected graph are used
to discuss the applications of the graph parameters Wiener index, the
detour index, the hyper-Wiener index and the hyper-detour index to
a class of graphs viz. bridge and chain graphs, which in turn, capture
different aspects of certain molecular graphs associated to the molecules
arising in special situations of molecular problems in theoretical Chemistry.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 309
For more applications of these paramters, one may refer to [13] and the
references therein.
The following theorems are used in the sequel.
Theorem 1.1. [7] Every end vertex of a connected graph G belongs to
each detour set of G. Also if the set S of all end vertices of G is a detour
set, then S is the unique minimum detour set of G.
Theorem 1.2. [7] If G is a connected graph of order n and detour
diameter D, then dn(G) ≤ n − D + 1.
Theorem 1.3. [7] Let G be a connected graph of order n ≥ 4. Then
dn(G) = n − 1 if and only if G = K1,n−1.
Theorem 1.4. [7] Let G be a connected graph of order n ≥ 5. Then
dn(G) = n − 2 if and only if G is a double star or K1,n−1 + e.
2. Detour hull number of a graph
A set S of vertices is a detour convex set if ID[S] = S. The detour
convex hull [S]D of S in G is the smallest detour convex set containing S.
The detour convex hull of S can also be formed from the sequence {Ik
D[S]}
(k ≥ 0), where I0
D[S] = S, I1
D[S] = ID[S] and Ik
D[S] = ID[Ik−1
D [S]]. From
some term on, this sequence must be constant. Let p be the smallest
number such that Ip
D[S] = Ip+1
D [S]. Then Ip
D[S] is the detour convex hull
[S]D. A set S of vertices of G is a detour hull set if [S]D = V and a detour
hull set of minimum cardinality is the detour hull number dh(G).
Example 2.1. For the graph G given in Figure 1, and S = {v1, v6},
ID[S] = V − {v7} and I2
D[S] = V . Thus S is a minimum detour hull set
of G and so dh(G) = 2. Since S is not a detour set and S ∪ {v7} is a
detour set of G, it follows from Theorem 1.1 that dn(G) = 3. Hence the
detour number and detour hull number of a graph are different. Note that
the sets S1 = {v1, v2} and S2 = {v2, v3, v4, v5, v7} are detour convex sets
in G.
Definition 2.2. A vertex v in a connected graph G is a detour extreme
vertex if it is an initial or terminal vertex of any detour in G containing
the vertex v.
Observation 2.3. A vertex v is detour extreme vertex if and only if
V (G) − {v} is a detour convex set in G.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
310 The detour hull number of a graph
Figure 1. G
Remark 2.4. Every end vertex of a graph G is a detour extreme vertex.
However, there are detour extreme vertices which are not end vertices. For
the graph G in Figure 2, w is a detour extreme vertex of G of degree 2.
Figure 2. G
It is defined in [7] that a vertex v in a connected graph G is a detour
vertex if it belongs to every minimum detour set of G. It is clear that
every detour extreme vertex is a detour vertex. However, a detour vertex
need not be a detour extreme vertex. For the graph H in Figure 2, the set
S = {u, v, w} is the unique detour set of H and so w is a detour vertex
of G. Since w lies on an x − y detour in H, w is not a detour extreme
vertex.
Proposition 2.5. Each detour extreme vertex of a nontrivial connected
graph G belongs to every detour hull set of G. In particular, each detour
extreme vertex belongs to every detour set of G.
Proof. Let x be a detour extreme vertex of G. Then x is either an initial
or terminal vertex of any detour containing the vertex x in G. Hence it
follows that x belongs to every detour hull set of G. Also, since every
detour set is a detour hull set, we see that each detour extreme vertex
belongs to every detour set of G.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 311
It is clear that the set of all end vertices of a nontrivial tree is a detour
set as well as a detour hull set and so we have the following corollary.
Corollary 2.6. If T is a tree with k end vertices, then dh(T ) = dn(T ) = k.
Proposition 2.7. For a connected graph G of order n, 2 ≤ dh(G) ≤
dn(G) ≤ n.
Proof. This follows from the fact that every detour set is a detour hull
set and any detour hull set contains at least 2 vertices.
Proposition 2.8. If a connected graph G 6= K2 has a full degree vertex
v, then v is not a detour extreme vertex of G.
Proof. Suppose that v is a detour extreme vertex of G. Let u, u′ be two
vertices such that D(u, u′) = diamD(G). Let P : u = u0, u1, . . . , uk = u′
be a detour diameteral path in G. Then N(u) ⊆ V (P ) and N(u′) ⊆ V (P ).
If u = v or u′ = v, say u = v, then P is a Hamiltonian path. Hence the
path P together with the edge vu′ is a Hamiltonian cycle in G and so
v ∈ ID[u1, u2], which is a contradiction to the fact that v is a detour
extreme vertex of G. So, assume that u 6= v and u′ 6= v. This implies
that v ∈ N(u) ⊆ V (P ), which is again a contradiction. Hence the result
follows.
Theorem 2.9. For each pair of positive integers r and s, there is a
connected graph G with r detour extreme vertices each of degree s.
Proof. If s = 1, then G = K1,r has the desired properties. Assume that
s = 2. For each i = 1, 2, 3, let P i
4 be a ui −vi vertex disjoint paths of order
4. Let H1 be the graph obtianed from P i ′
4 s by identifying the vertices
u1, u2, u3 as u and identifying the vertices v1, v2, v3 as v. Let H2 be the
totally disconnected graph Kr on r vertices such that H1 and H2 are
vertex disjoint. Let G be the graph obtained from H1 and H2 by joining
each vertex of H2 to both u and v. The graph G is shown in Figure 3.
We claim that V (G) − {w} is a detour convex set for each w ∈ V (H2).
Let w ∈ V (H2). If r = 1 or r = 2, then w /∈ ID[x, y] for x, y ∈ V (H2)
with w 6= x, y. For r ≥ 3, it is clear that D(x, y) = 5 for all x, y ∈ V (H2)
and any x − y path which contains w with w 6= x, y has length 4. Hence
w /∈ ID[x, y] for all x, y ∈ V (H2) − {w}. Also, we have D(u, v) = 3 and
P : u, w, v is the unique u − v path which contains w. Thus w /∈ ID[u, v].
Let x, y ∈ V (H1) − {u, v}. If x and y are adjacent, then D(x, y) = 5
and any x − y path that contains w has length 4. Also, if x and y are
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
312 The detour hull number of a graph
Figure 3. G
nonadjacent, then D(x, y) = 6 or D(x, y) = 7; and any x − y path that
contains w has length D(x, y) − 1. Hence it follows that V (G) − {w} is a
detour convex set and so w is a detour extreme vertex of G. Thus G has
r detour extreme vertices, each of degree 2.
Assume that s ≥ 3. Let Ms be the complete multigraph with V (Ms) =
{w1, w2, . . . , ws} such that there are exactly two edges between every pair
of distinct vertices of Ms. Subdividing each edges of Ms twice, we obtain
a graph S2(Ms). For each pair i, j of integers with 1 ≤ i < j ≤ s, let
wi, uijl, vijl, wj (l = 1, 2) be the two wi − wj path of length 3 in S2(Ms).
Let H be the totally disconnected graph on r vertices Kr such that S2(Ms)
and H are vertex disjoint. Let G be the graph obtained from S2(Ms) and
H by joining each vertex w of H to each of the vertices wi(1 ≤ i ≤ s).
The graph G is shown in Figure 4 for s = 3. We show that every vertex of
H is detour extreme. We prove this for the case when s = 3 only, since the
argument for s ≥ 4 is similar. Let w ∈ V (H). If r = 1 or r = 2, then it is
clear that w /∈ ID[x, y], where x, y ∈ V (H) with w 6= x, y. For r ≥ 3, it is
clear that any x − y path containing the vertex w has length at most 7 for
x, y ∈ V (H) − {w}. Since D(x, y) = 8 for all x, y ∈ V (H), it follows that
w /∈ ID[x, y] for all x, y ∈ V (H) − {w}. Also, D(uijl, vijl) = 8 and any
uijl − vijl path containing the vertex w is of length at most 7. Similarly,
D(uij1, vij2) = 10 and any uij1 − vij2 path containing the vertex w is of
length at most 9. Similarly, for the other vertices, it can be easily checked
that any x − y path containing the vertex w with w 6= x, y is of length at
most D(x, y) − 1. Hence it follows that w is a detour extreme vertex of
G. Thus, G has r detour extreme vertices each of degree s.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 313
Figure 4. G
Theorem 2.10. For each pair a, b of integers with 2 ≤ a ≤ b, there is a
connected graph G with dh(G) = a and dn(G) = b.
Proof. If a = b, then K1,a has the desired properties. So, assume that
a < b. Let Gi(1 ≤ i ≤ b − a) be the graph given in Figure 5. If b − a = 1,
then H = G1. If b − a ≥ 2, then let H be the graph obtained from the
G ′
i s by identifying the vertices vi, ui+1(1 ≤ i ≤ b − a − 1). Let G be the
graph obtained from H by adding a − 1 new vertices s1, s2, . . . , sa−1 and
joining each si(1 ≤ i ≤ a − 1) to vb−a. We show that the graph G has
the desired properties. Let S = {u1, s1, s2, . . . , sa−1} be the set of end
vertices of G. Then it is clear that ID[S] = V − {w1, w2, . . . , wb−a} and
I2
D[S] = V . Hence by Proposition 2.5, S is a minimum detour hull set
of G so that dh(G) = a. Now, each wi(1 ≤ i ≤ b − a) lies only on the
xi − zi, xi − ti, yi − ti and yi − zi detours and so wi is a detour vertex
of G. Since S ∪ {w1, w2, . . . , wb−a} is a detour set of G, it follows from
Proposition 2.5 that dn(G) = b.
Lemma 2.11. Let S be a minimum detour hull set of a connected graph
G and let u, v ∈ S. If w is a vertex distinct from u and v such that it lies
on a u − v detour in G, then w /∈ S.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
314 The detour hull number of a graph
Figure 5. Gi
Proof. If w ∈ S, then S ⊆ ID[S − {w}] and hence S − {w} is a detour
hull set of G, which is a contradiction to S a minimum detour hull set of
G. Thus the result follows.
Theorem 2.12. Let G be a connected graph with a cut vertex v and S
a detour hull set of G. Then
(i) Every component of G − v contains an element of S.
(ii) If S is a minimum detour hull set of G, then no cut vertex of G belongs
to S.
Proof. (i). Let C be a component of G − v. Since v is a cut vertex, it is
clear that V (G) − V (C) is a detour convex set of G. Hence it follows that
V (C) ∩ S 6= φ.
(ii). Let S be a minimum detour hull set of G and let C1, C2, . . . , Ck
(k ≥ 2) be the components of G − v. By (i), we see that V (Ci) ∩ S 6= φ for
i = 1, 2, . . . , k. Since v is a cut vertex of G, it follows that v ∈ ID[u1, u2],
where u1 ∈ V (C1) ∩ S and u2 ∈ V (C2) ∩ S. Now, it follows from Lemma
2.11 that v /∈ S. This completes the proof.
Corollary 2.13. If G is a connected graph having k ≥ 2 end-blocks, then
dh(G) ≥ k.
Theorem 2.14. Let G be a connected graph with p end vertices and
k end-blocks B1, B2, . . . , Bk such that |V (Bi)| ≥ 3 for 1 ≤ i ≤ k. If
dh(Bi) = ki, then dh(G) ≥ p + (
∑k
i=1 ki) − k.
Proof. If k = 0, then by Proposition 2.5, the result follows. If p = 0
and k = 1, then the graph G itself is a block and the result follows.
For the remaining cases, assume to the contrary that there exists a
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 315
connected graph G with p end vertices and k end-blocks B1, B2, . . . , Bk
such that |V (Bi)| ≥ 3 and dh(Bi) = ki (1 ≤ i ≤ k) for which dh(G) ≤
p + (
∑k
i=1 ki) − k − 1. Then G contains a detour hull set S of cardinality
p + (
∑k
i=1 ki) − k − 1. Consequently, at least one of the end-blocks Bi
contains no more than ki − 2 vertices of S. Without loss of generality, let
B1 contain at most k1 − 2 vertices of S and let S1 = S ∩ V (B1) ∪ {v},
where v ∈ V (B1) is the cut vertex of G. Then |S1| ≤ k1 − 1 and S1
is not a detour hull set of B1. Hence there exists u ∈ V (B1) such that
u /∈ In
D[S1]B1
for any n ≥ 0. Now, we claim that In
D[S] ∩ V (B1) ⊆ In
D[S1]
for any n ≥ 0. We prove this by induction on n. If n = 0, then the claim
is obvious. Let x ∈ ID[S] ∩ V (B1). If x ∈ S, then x ∈ S1 ⊆ ID[S1]. So,
assume that x /∈ S. We have x ∈ ID[y, z] for some y, z ∈ S. If x = v,
then x ∈ S1 and so x ∈ ID[S1]. Let x 6= v. Since B1 is an end-block, it
follows that at least one of y and z, say y belongs to B1 and so y ∈ S1. If
z ∈ V (B1), then z ∈ S1 and so x ∈ ID[S1]. So, assume that z /∈ V (B1).
Let P be a y − z detour which contains the vertex x. Then the y − v
subpath Q of P is a y − v detour in G. Hence x ∈ ID[y, v] ⊆ ID[S1]. Thus
ID[S] ∩ V (B1) ⊆ ID[S1]. Now, assume that the result is true for n = k.
Then Ik
D[S] ∩ V (B1) ⊆ Ik
D[S1]. Let x ∈ Ik+1
D [S] ∩ V (B1). If x ∈ Ik
D[S],
then by induction hypothesis, x ∈ Ik
D[S1], which is a subset of Ik+1
D [S1],
and so we are through. So, assume that x /∈ Ik
D[S]. Then x ∈ ID[y, z]
for some y, z ∈ Ik
D[S]. Since x ∈ V (B1), as above, we see that at least
one of y and z, say y belongs to V (B1). Hence by induction hypothesis,
y ∈ Ik
D[S1]. If z ∈ V (B1), then again by induction hypothesis, z ∈ Ik
D[S1]
and so x ∈ Ik+1
D [S1]. If z /∈ V (B1), then x ∈ ID[y, v] with y ∈ Ik
D[S1] and
v ∈ S1. Since S1 ⊆ Ik
D[S1], we see that x ∈ Ik+1
D [S1]. Thus by induction
In
D[S] ∩ V (B1) ⊆ In
D[S1] for all n ≥ 0. Now, since S is a detour hull set
of G, there is an integer r ≥ 0 such that Ir
D[S] = V (G). This implies
that V (B1) ⊆ Ir
D[S1]. Also, since B1 is an end-block of G, it is clear
that In
D[S1] = In
D[S1]B1
for all n ≥ 0 and so Ir
D[S]B1
= V (B1). This is
a contradiction to the fact that u /∈ In
D[S1]B1
for any n ≥ 0. Hence the
result follows.
Remark 2.15. The lower bound in Theorem 2.14 is strict. For the
graph G in Figure 6, each of the k end-blocks Bi is such that dh(Bi) =
2. Note that x is a detour extreme vertex of G. Since the set S =
{u1, u2, . . . , up, x, v1, v2, . . . , vk} is a detour hull set, it follows from Propo-
sition 2.5 and Theorem 2.12 that dh(G) = p + k + 1 and so the bound
in Theorem 2.14 is strict. Also, for the graph H = G − x, we have
dh(G) = p + k and so the lower bound in Theorem 2.14 is sharp.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
316 The detour hull number of a graph
Figure 6. G
Theorem 2.16. Let G be a unicyclic graph with the cycle C and k ≥ 1
end vertices. Then
dh(G) =
{
k + 1 if exactly one vertex of C has degree ≥ 3
k otherwise.
Proof. Let S = {u1, u2, . . . , uk} be the set of end vertices of G. For
each vertex ui, there exists a unique vertex vi in C such that d(ui, vi) is
minimum. If exactly one vertex of C has degree ≥ 3, then v1 = v2 = · · · =
vk = v, say. Then it can be easily seen that [S]D contains at most the
vertex v from C and so S is not a detour hull set. Let v′ be a vertex in
C such that v′ is adjacent to v. Then ID[S ∪ {v′}] = V and so it follows
from Proposition 2.5 that S ∪ {v′} is a minimum detour hull set of G and
so dh(G) = |S| + 1 = k + 1. Now, assume that C has at least two vertices
of degree ≥ 3. Since G is unicyclic, it is clear that ID[vi, vj ] ⊆ ID[ui, uj ]
for vi 6= vj . Let Pi be the ui − vi path in G and let Qij be a vi − vj
detour in G. Then V (Qij) ⊆ V (C), and for vi 6= vj , Pi together with Qij
followed by Pj is a ui − uj detour in G. Now, let x be a vertex of G. If
x /∈ V (C), then x ∈ V (Pi) for some i with 1 ≤ i ≤ k. Since C has at least
two vertices of degree ≥ 3, it follows that x ∈ ID[ui, uj ] for some j with
1 ≤ i 6= j ≤ k. Now, let x ∈ V (C). Let v and v′ be vertices in C such that
deg(v) ≥ 3 and deg(v′) ≥ 3. Then v = vr and v′ = vs for some r, s with
1 ≤ r 6= s ≤ k. If x ∈ Qrs, then x ∈ ID[ur, us]. Otherwise, x ∈ ID[v′, y],
where v′, y ∈ V (Qrs) such that v′ and y are adjacent. Thus we see that
x ∈ I2
D[ur, us]. Hence it follows from Proposition 2.5 that S is a minimum
detour hull set of G and so dh(G) = |S| = k.
3. The detour hull number and the detour number
The following theorem is an immediate consequence of Theorem 1.2.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 317
Theorem 3.1. If G is a connected graph of order n and detour diameter
D, then dh(G) ≤ n − D + 1.
We give below a characterization theorem for trees.
Theorem 3.2. For every non-trivial tree T of order n and detour diameter
D, dh(T ) = n − D + 1 if only if T is a caterpillar.
Proof. Let T be any non-trivial tree. Let u, v be two vertices in T such that
D(u, v) = D and P : u = v0, v1, . . . , vD−1, vD = v be a detour diameteral
path. Let k be the number of end-vertices of T and l the number of
internal vertices of T other than v1, v2, . . . , vD−1. Then D − 1 + l + k = n.
By Corollary 2.6, dh(T ) = k = n − D − l + 1. Hence dh(T ) = n − D + 1
if and only if l = 0, if and only if all the internal vertices of T lie on the
detour diameteral path P , if and only if T is a caterpillar.
Theorem 3.3. For each triple D, k and n of positive integers with 2 ≤
k ≤ n − D + 1 and D ≥ 3, there is a connected graph G of order n, detour
diameter D and detour hull number k.
Proof. Let G be the graph obtained from the cycle CD : u1, u2, . . . , uD, u1
of order D by (1) adding k − 1 new vertices v1, v2, . . . , vk−1 and joining
each vertex vi(1 ≤ i ≤ k − 1) to u1 and (2) adding n − D − k + 1
new vertices w1, w2, . . . , wn−D−k+1 and joining each vertex wi(1 ≤ i ≤
n − D − k + 1) to both u1 and u3. The graph G has order n and detour
diameter D and is shown in Figure 7. Now, we show that dh(G) = k.
Figure 7. G
Let S = {v1, v2, . . . , vk−1} be the set of end vertices of G. It is clear that
ID[S] = S ∪ {u1} and I2
D[S] = ID[S]. Thus [S]D = S ∪ {u1} 6= V and so
S is not a detour hull set of G. Since ID[S ∪ {uD}] = V , it follows from
Proposition 2.5 that S ∪ {uD} is a minimum detour hull set of G so that
dh(G) = |S| + 1 = k.
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
318 The detour hull number of a graph
It is proved in [2] that the detour radius and detour diameter of a
connected graph G satisfy radD(G) ≤ diamD(G) ≤ 2 radD(G). It is also
proved that every pair a, b of positive integers can be realized as the
detour radius and detour diameter respectively of some connected graph,
provided a ≤ b ≤ 2a. We extend this theorem so that the detour hull
number can be prescribed as well, when a < b ≤ 2a.
Theorem 3.4. For positive integers a, b and k ≥ 2 with a < b ≤ 2a,
there exists a connected graph G with radD(G) = a, diamD(G) = b and
dh(G) = b.
Proof. If a = 1 and b = 2, then G = K1,k has the desired properties.
So, let a ≥ 2. Let Ka and Kb−a be the complete graphs of order a and
b − a respectively such that both are vertex disjoint. Let H be the graph
obtained by identifying a vertex v of Ka and Kb−a. Let H1 be the graph
obtained from H by adding k −1 new vertices u1, u2, . . . , uk−1 and joining
each ui(1 ≤ i ≤ k − 1) to a vertex x 6= v of Ka. Now, if b − a = 1,
then G be the graph obtained from H1 by adding a new vertex uk and
joining it to v; if b − a ≥ 2, then G be the graph obtained from H1
by adding a new vertex uk and joining it to a vertex y 6= v of Kb−a.
Then it is clear that the set S = {u1, u2, . . . , uk} of end vertices of G is
a detour hull set of G and so by Proposition 2.5, dh(G) = k. Note that
D(v, z) =
a − 1 if z ∈ V (Ka) and z 6= v,
a if z = ui(1 ≤ i ≤ k − 1),
b − a − 1 if z ∈ V (Kb−a) and z 6= uk,
b − a if x = uk.
Since b ≤ 2a, we have b−a ≤ a. Hence it follows that eD(v) = a. Similarly,
it can be easily seen that eD(ui) = b for i = 1, 2, . . . , k and eD(x) = b − 1
for all x 6= v, ui(1 ≤ i ≤ k). Hence it follows that radD(G) = a and
daimD(G) = b.
A graph G is said to be hypohamiltonian if G does not itself have a
Hamiltonian cycle but every graph formed by removing a single vertex
from G is Hamiltonian.
Proposition 3.5. If G is a Hamiltonian or hypohamiltonian graph, then
dn(G) = dh(G) = 2.
Proof. If G is Hamiltonian, then G has a Hamiltonian cycle C. Then any
two adjacent vertices in C is a detour set as well as a detour hull set of G
and so dn(G) = dh(G) = 2. If G is a hypohamiltonian graph, then for any
vertex v, G − v has a Hamiltonian cycle C : u1, u2, . . . , un−1, u1, where u1
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 319
is adjacent to v. Now, P : v, u1, u2, . . . , un−1 is a v − un−1 Hamiltonian
path in G. Hence S = {v, un−1} is a detour set as well as a detour hull
set of G and so dn(G) = dh(G) = 2.
Now, we introduce two classes of graphs Γ and Ω given in Figures 8
and 9, respectively, which are used in the proof of Theorem 3.6.
Figure 8. Γ
Theorem 3.6. If G is a connected graph with diamD(G) ≤ 4, then
dn(G) = dh(G).
Proof. If diamD(G) = 1, then G = K2 and so the result follows. Also, if
diamD(G) = 2, then G = K1,n(n ≥ 2) or G = K3 and so dn(G) = dh(G).
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
320 The detour hull number of a graph
Figure 9. Ω
Now, let diamD(G) = 3. If G is a tree, then by Corollary 2.6, dn(G) =
dh(G). So, assume that cir(G) ≥ 3, where cir(G) denotes the length of
a longest cycle in G. Since diamD(G) = 3, it is clear that cir(G) = 3
or cir(G) = 4. If cir(G) = 4, then G = C4 or G = C4 + e or G = K4
and so the result follows from Proposition 3.5. Let cir(G) = 3. Then
the graph G reduces to G = K1,n−1 + e and so it is easily seen that
dn(G) = dh(G). Now, let diamD(G) = 4. If G is a tree, then the result
follows. Assume that G is not a tree. Since diamD(G) = 4, we have
cir(G) ≤ 5. If cir(G) = 3, then G belongs to the family Γ. Hence it
follows from Proposition 2.5 and Theorem 2.12 that dn(G) = dh(G) for
each G in Γ. Let cir(G) = 4. Then it is clear that G belongs to the family
Ω. It follows from Proposition 2.5 and Theorem 2.12 that dn(G) = dh(G)
for each G in Ω. Now, let cir(G) = 5. Since diamD(G) = 4, it follows
that order of G is 5 and hence G is Hamiltonian. Then it follows from
Proposition 3.5 that dn(G) = dh(G). This completes the proof.
Theorem 3.7. Let G be a connected graph of order n ≥ 4. Then the
following are equivalent:
(i) dh(G) = n − 1
(ii) dn(G) = n − 1
(iii) G = K1,n−1
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
A.P. Santhakumaran, S.V. Ullas Chandran 321
Proof. By Theorem 1.3, it is enough to prove that (i) and (ii) are equivalent.
Suppose that dh(G) = n − 1. Then by Theorem 3.1, diamD(G) ≤ 2 and
so it follows from Theorem 3.6 that dn(G) = n − 1. Conversely, Suppose
that dn(G) = n − 1. Then by Theorem 1.2, diamD(G) ≤ 2 and so it
follows from Theorem 3.6 that dh(G) = n − 1.
Theorem 3.8. Let G be a connected graph of order n ≥ 5. Then the
following are equivalent:
(i) dh(G) = n − 2
(ii) dn(G) = n − 2
(iii) G is a double star or G = K1,n−1 + e
Proof. By Theorem 1.4, it is enough to prove that (i) and (ii) are equivalent.
Suppose that dh(G) = n − 2. Then by Theorem 3.1, diamD(G) ≤ 3 and
so it follows from Theorem 3.6 that dn(G) = n − 2. Conversely, Suppose
that dn(G) = n − 2. Then by Theorem 1.2, diamD(G) ≤ 3 and so it
follows from Theorem 3.6 that dh(G) = n − 2.
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, F. Harary and P. Zhang, On the hull number of a graph, Ars
Combin., 57(2000), 129-138.
[4] G. Chartrand, P.Zhang, Extreme geodesic graphs, Czechoslovak Mathematical
Journal, 52(127)(2002), 771 - 780.
[5] G. Chartrand, F. Harary and P. Zhang, On the Geodetic Number of a Graph,
Networks, 39(1)(2002), 1-6.
[6] G. Chartrand, J. F. Fink and P. Zhang, On the hull Number of an oriented graph,
Int. J. Math. Math Sci., 36 (2003), 2265-2275.
[7] G. Chartrand, G.L. Johns, and P. Zhang, Detour Number of a Graph, Util. Math.
64 (2003), 97–113.
[8] G. Chartrand, L. Nebesky, and P. Zhang, A Survey of Hamilton Colorings of
Graphs, Preprint.
[9] G. Chartrand and P. Zhang, Introduction to Graph Theory, Tata McGraw- Hill
Edition, New Delhi,2006.
[10] M. Grötschel, Hypohamiltonian facets of the symmetric travelling salesman poly-
tope, Zeitschrift für Angewandte Mathematik und Mechanik, 58(1977), 469-471.
[11] M. G. Everett and S. B. Seidman, The hull number of a graph, Discrete Math.,
57(1985), 217-22
Jo
ur
na
l
A
lg
eb
ra
D
is
cr
et
e
M
at
h.
322 The detour hull number of a graph
[12] W. Hale, Frequency Assignment; Theory and Applications, Proc. IEEE 68 (1980),
1497–1514.
[13] T. Mansour and M. Schork, Wiener, hyper-Wiener detour and hyper-detour indices
of bridge and chain graphs, J. Math. Chem., 47(2010) 72-98.
[14] A. P. Santhakumaran and S. Athisayanathan, Connected detour number of a
graph, J. Combin. Math. Combin. Comput., 69 (2009), 205-218.
Contact information
A.P.
Santhakumaran
Department of Mathematics, Hindustan Uni-
versity, Hindustan Institute of Technology and
Science, Chennai - 603 103, India
E-Mail: apskumar1953@yahoo.co.in
S.V. Ullas
Chandran
Department of Mathematics, Amrita Vishwa
Vidyapeetham University, Amritapuri Campus,
Kollam - 690 525, India
E-Mail: ullaschandra01@yahoo.co.in
Received by the editors: 16.03.2011
and in final form 03.01.2012.
|
| id | nasplib_isofts_kiev_ua-123456789-152246 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-01T04:11:46Z |
| publishDate | 2012 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Santhakumaran, A.P. Ullas Chandran, S.V. 2019-06-09T06:15:01Z 2019-06-09T06:15:01Z 2012 The detour hull number of a graph / A.P. Santhakumaran, S.V. Ullas Chandran // Algebra and Discrete Mathematics. — 2012. — Vol. 14, № 2. — С. 307–322. — Бібліогр.: 14 назв. — англ. 1726-3255 2010 MSC:05C12. https://nasplib.isofts.kiev.ua/handle/123456789/152246 For vertices u and v in a connected graph G = (V, E), the set ID[u, v] consists of all those vertices lying on a u−v longest path in G. Given a set S of vertices of G, the union of all sets ID[u, v] for u, v ∈ S, is denoted by ID[S]. A set S is a detour convex set if ID[S] = S. The detour convex hull [S]D of S in G is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among the subsets S of V with [S]D = V. A set S of vertices is called a detour set if ID[S] = V. The minimum cardinality of a detour set is the detour number dn(G) of G. A vertex x in G is a detour extreme vertex if it is an initial or terminal vertex of any detour containing x. Certain general properties of these concepts are studied. It is shown that for each pair of positive integers r and s, there is a connected graph G with r detour extreme vertices, each of degree s. Also, it is proved that every two integers a and b with 2 ≤ a ≤ b are realizable as the detour hull number and the detour number respectively, of some graph. For each triple D, k and n of positive integers with 2 ≤ k ≤ n − D + 1 and D ≥ 2, there is a connected graph of order n, detour diameter D and detour hull number k. Bounds for the detour hull number of a graph are obtained. It is proved that dn(G) = dh(G) for a connected graph G with detour diameter at most 4. Also, it is proved that for positive integers a, b and k ≥ 2 with a < b ≤ 2a, there exists a connected graph G with detour radius a, detour diameter b and detour hull number k. Graphs G for which dh(G) = n − 1 or dh(G) = n − 2 are characterized. Research supported by DST Project No. SR/S4/MS: 319/06 en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics The detour hull number of a graph Article published earlier |
| spellingShingle | The detour hull number of a graph Santhakumaran, A.P. Ullas Chandran, S.V. |
| title | The detour hull number of a graph |
| title_full | The detour hull number of a graph |
| title_fullStr | The detour hull number of a graph |
| title_full_unstemmed | The detour hull number of a graph |
| title_short | The detour hull number of a graph |
| title_sort | detour hull number of a graph |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/152246 |
| work_keys_str_mv | AT santhakumaranap thedetourhullnumberofagraph AT ullaschandransv thedetourhullnumberofagraph AT santhakumaranap detourhullnumberofagraph AT ullaschandransv detourhullnumberofagraph |