J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
1Ae9.
ON THE DETOUR AND VERTEX DETOUR HULL
NUMBERS OF A GRAPH
Santhakumaran1 and S.
Ullas Chandran2 Department of Mathematics Hindustan University Hindustan Institute of Technology and Science.
Padur.
Chennai - 603 103.
India apskumar1953@yahoo.
Department of Mathematics.
Mahatma Gandhi College.
Kesavdasapuram.
Pattom P.
Thiruvanathapuram - 695 004.
India math@gmail.
Abstract.
For vertices x and y in a connected graph G, the detour distance D.
, .
is the length of a longest x Oe y path in G.
An x Oe y path of length D.
, .
is an x Oe y detour.
The closed detour interval ID .
, .
consists of x, y, and all vertices lying on some x Oe y detour of G.
while for S OI V (G).
ID [S] = x,yOOS ID .
, .
A set S of vertices is a detour convex set if ID [S] = S.
The detour convex hull [S]D is the smallest detour convex set containing S.
The detour hull number dh(G) is the minimum cardinality among subsets S of V (G) with [S]D = V (G).
Let x be any vertex in a connected graph G.
For a vertex y in G, denote by IG .
x , the set of all vertices distinct from x that lie on some x Oe y detour of G.
for S OI V (G).
ID [S]x = yOOS ID .
For x OO / S.
S is an x-detour set of G if ID [S]x = V (G) Oe .
and an x-detour set of minimum cardinality is the x-detour number dx (G) of G.
For x OO / S.
S is an x-detour convex set if ID [S]x = S.
The x-detour convex hull of S, [S]x D is the smallest x-detour convex set containing S.
The x-detour hull number dhx (G) is the minimum cardinality among the subsets S of V (G) Oe .
with [S]x D = V (G) Oe .
In this paper, we investigate how the detour hull number and the vertex detour hull number of a connected graph are affected by adding a pendant edge.
Key words and Phrases:d Detour, detour number, detour hull number, x-detour number, x-detour hull number.
2000 Mathematics Subject Classification: 05C12 Received: 27-08-2013, revised: 21-01-2014, accepted: 21-01-2014.
Santhakumaran and S.
Ullas Chandran Abstrak.
Misalkan x dan y berada di graf terhubung G, jarak detour D.
, .
adalah panjang dari lintasan x Oe y yang terpanjang di G.
Lintasan x Oe y dengan panjang D.
, .
adalah suatu detour xOey.
Interval detour tertutup ID .
, .
memuat x, y dan semua titik yang berada dalam suatu detour x Oe y dari G.
sedangkan untuk S OI V (G).
ID [S] = x,yOOS ID .
, .
Himpunan titik S adalah suatu himpunan konveks detour jika ID [S] = S.
Konveks hull detour [S]D adalah himpunan konveks detour terkecil yang memuat S.
Bilangan hull detour dh(G) adalah kardinalitas minimum diantara sub-subhimpunan S dari V (G) dengan [S]D = V (G).
Misalkan x adalah suatu titik di graf terhubung G.
Untuk suatu titik y di G, dinotasikan dengan IG .
x , himpunan dari semua titik berbeda dari x yang terletak pada suatu detour x Oe y dari G.
sedangkan untuk S OI V (G).
ID [S]x = yOOS ID .
Untuk xOO / S.
S adalah suatu himpuan detour-x dari G jika ID [S] = V (G)Oe.
dan suatu himpuan detour-x dengan kardinalitas minimum adalah bilangan detour-x dx (G) dari G.
Untuk x OO / S.
S adalh suatu himpunan detour-x konveks jika ID [S]x = Konveks hull detour-x dari S, [S]x D adalah himpunan konveks detour-x yang memuat S.
Bilangan hull detour-x dhx (G) adalah kardinalitas minimum diantara sub-subhimpunan S dari V (G) Oe .
dengan [S]x D = V (G) Oe .
Pada paper ini, kami memeriksa pengaruh penambahan sisi anting dari suatu graf terhubung terhadap bilangan hull detour dan bilangan hull detour titik.
Kata kunci: Detour, bilangan detour, bilangan hull detour, bilangan detour-x, bilangan hull detour-x.
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 n and m respectively.
For basic definitions and terminologies, we refer to .
, .
For vertices x and y in a nontrivial connected graph G, the detour distance D.
, .
is the length of a longest x Oe y path in G.
An x Oe y path of length D.
, .
is an x Oe y detour.
It is known that the detour distance is a metric on the vertex set V (G).
The detour eccentricity of a vertex u is eD .
=max{D.
, .
: v OO V (G)}.
The detour radius, rad D (G) of G is the minimum detour eccentricity among the vertices of G, while the detour diameter, diam D (G) of G is the maximum detour eccentricity among the vertices of G.
The detour distance and the detour center of a graph were studied in .
The closed detour interval ID .
, .
consists of x,Sy, and all vertices lying on some x Oe y detour of G.
while for S OI V (G).
ID [S] = x,yOOS ID .
, .
S is a detour set if ID [S] = V (G) and a detour set of minimum cardinality is the detour number dn(G) of G.
Any detour set of cardinality dn(G) is the minimum detour set or dn-set of A vertex x in G is a detour extreme vertex if it is an initial or terminal vertex of any detour containing x.
The detour number of a graph was introduced in .
and further studied in .
, .
These concepts have interesting applications in Channel Assignment Problem in radio technologies .
, .
On the Detour and Vertex Detour Hull Numbers A set S of vertices of a graph G is a detour convex set if ID [S] = S.
The detour convex hull [S]D of S is the smallest detour convex set containing S.
The detour convex hull of S can also be formed from the sequence {ID [S], k Ou .
, where kOe1 [S] = S.
[S] = ID [S] and ID = ID [ID [S]].
From some term on, this sequence must be constant.
Let p be the smallest number such that ID
[S] = ID
[S].
Then ID [S] is the detour convex hull [S]D and we call p as the detour iteration number din(S) of S.
A set S of vertices of G is a detour hull set if [S]D = V (G) and a detour hull set of minimum cardinality is the detour hull number dh(G).
The detour hull number of a graph was introduced and studied in .
For the graph G given in Figure 1, and S = .
1 , v6 }.
ID [S] = V Oe .
7 } and [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 O .
7 } is a detour set of G, it follows from Theorem 1.
that dn(G) = 3.
Hence the detour number and detour hull number of a graph are Note that the sets S1 = .
1 , v2 } and S2 = .
2 , v3 , v4 , v5 , v7 } are detour convex sets in G.
Let x be any vertex of G.
For a vertex y in G.
IG .
x denotes Figure 1.
Graph G with dh (G) = 2 and dn(G) = 3 the set of all vertices S distinct from x that lie on some x Oe y detour of G.
while for S OI V (G).
ID [S]x = yOOS ID .
It is clear that ID .
x = I.
For x OO / S.
S is an x-detour set if ID [S]x = V (G) Oe .
and an x-detour set of minimum cardinality is the x-detour number dx (G) of G.
Any x-detour set of cardinality dx (G) is the minimum x-detour set or dx -set of G.
The vertex detour number of a graph was introduced and studied in .
Let G be a connected graph and x a vertex in G.
Let S be a set of vertices in G such that x OO / S.
Then S is an x-detour convex set if ID [S]x = S.
The x-detour convex hull of S, [S]xD is the smallest x-detour convex set containing S.
The x-detour convex set can also formed from the sequence {ID [S]x , k Ou .
, where kOe1 [S]x = S.
ID [S]x = ID [S]x and ID [S]x = ID [ID [S]x ]x .
From some term on, this sequence must be constant.
Let px be the smallest number such that ID [S]x = ID [S] .
Then ID [S] is the x-detour convex hull [S]D of S and we call px as the x-detour iteration number dinx (S) of S.
The set S is an x-detour hull set if [S]xD = V (G) Oe .
and an x-detour hull set of minimum cardinality is the xdetour hull number dhx (G) of G.
Any x-detour hull set of cardinality dhx (G) is the minimum x-detour hull set or dx -hull set of G.
For the graph G in Figure 2, the minimum vertex detour hull numbers and vertex detour numbers are given in Table 1.
Table 1 shows that, for a vertex x, the x-detour number and the x-detour hull number of a graph are different.
Santhakumaran and S.
Ullas Chandran Figure 2.
Table 1.
x-detour numbers and x-detour hull numbers of G in Figure 2 It is clear that every minimum x-detour hull set of a connected graph G of order n contains at least one vertex and at most n Oe 1 vertices.
Also, since every x-detour set is a x-detour hull set, we have the following proposition.
Throughout this paper G denotes a connected graph with at least two vertices.
The following theorems will be used in the sequel.
Theorem 1.
Let G be a connected graph.
Then .
Each detour extreme vertex of G belongs to every detour hull set of G.
No cut vertex of G belongs to any minimum detour hull set of G.
Theorem 1.
Each end vertex of G other than x .
hether x is an end vertex or no.
belongs to every minimum x-detour set of G.
Theorem 1.
Let x be a vertex of a connected graph G.
Let S be any x-detour hull set of G.
Then .
Each x-detour extreme vertex of G belongs to S.
If v is a cut vertex of G and C a component of G Oe v such that x OO / V (C), then S O V (C) 6= OI.
No cut-vertex of G belongs to any minimum x-detour hull set of G.
Theorem 1.
For any vertex x in a connected graph G of order n, dhx (G) O n Oe eD .
Graphs of Order n with Vertex Detour Hull Number n Oe 1, n Oe 2 and n Oe 3 Theorem 2.
Let G be a connected graph of order n Ou 2.
Then dhx (G) = n Oe 1 for every vertex x in G if and only if G = K2 .
On the Detour and Vertex Detour Hull Numbers Proof.
Suppose that G = K2 .
Then dhx (G) = 1 = n Oe 1.
The converse follows from Theorem 1.
Theorem 2.
Let G be a connected graph of order n Ou 3.
Then dhx (G) = n Oe 2 for every vertex x in G if and only if G = K3 .
Proof.
Suppose that G = K3 .
Then it is clear that dhx (G) = 1 = n Oe 2 for every vertex x in G.
Conversely, suppose that dhx (G) = n Oe 2 for every vertex x in G.
Then by Theorem 1.
4, eD .
O 2 for every vertex x in G.
It follows from Theorem 1 that eD .
6= 1 for every vertex x in G.
Thus eD .
= 2 for every vertex x in G.
or the vertex set can be partitioned into V1 and V2 such that eD .
= 1 for x OO V1 and eD .
= 2 for x OO V2 .
Thus either radD (G) = diamD (G) = 2.
we have radD (G) = 1 and diamD (G) = 2.
This implies that either G = K3 or G = K1,nOe1 .
If G = K1,nOe1 , then by Theorem 1.
3, dhx (G) = n Oe 1 for the cut vertex x and dhy (G) = n Oe 2 for any end vertex y in G, which is a contradiction to the hypothesis.
Hence G = K3 .
Theorem 2.
Let G be a connected graph of order n Ou 2.
Then G = K1,nOe1 if and only if the vertex set V (G) can be partitioned into two sets V1 and V2 such that dhx (G) = n Oe 1 for x OO V1 and dhy (G) = n Oe 2 for y OO V2 .
Proof.
Suppose that G = K1,nOe1 .
Then dhx (G) = n Oe 1 for the cut vertex x in G and dhy (G) = n Oe 2 for any end vertex y in G.
Conversely, suppose that the vertex set V (G) can be partitioned into two sets V1 and V2 such that dhx (G) = n Oe 1 for x OO V1 .
and we have dhy (G) = nOe2 for y OO V2 .
Then by Theorem 1.
4, eD .
= 1 for each x OO V1 and eD .
= 1 or eD .
= 2 for each y OO V2 .
It follows from Theorem 1 that eD .
= 2 for some y OO V2 .
Hence radD (G) = 1 and diamD (G) = 2.
Thus G = K1,nOe1 .
Theorem 2.
Let G be a connected graph of order n Ou 5.
Then G is a double star or G = K1,nOe1 e if and only if the vertex set V (G) can be partitioned into two sets V1 and V2 such that dhx (G) = n Oe 2 for x OO V1 and dhy (G) = n Oe 3 for y OO V2 .
Proof.
Suppose that G is a double star or G = K1,nOe1 e.
Then it follows from Theorem 1.
3 that dhx (G) = n Oe 2 or dhx (G) = n Oe 3 according to whether x is a cut vertex of G or not.
Conversely, suppose that dhx (G) = n Oe 2 for x OO V1 and dhx (G) = n Oe 3 for x OO V2 .
Then by Theorem 1.
4, eD .
O 3 for every x and so diamD (G) O 3.
It follows from Theorem 2.
1 that G 6= K2 and so diamD (G) Ou 2.
If diamD (G) = 2, then G is the star K1,nOe1 and by Theorem 2.
3, dhx (G) = n Oe 1 or dhx (G) = n Oe 2 for every vertex x.
This is a contradiction to the hypothesis.
Now, suppose that diamD (G) = 3.
If G is a tree, then G is a double star.
If G is not a tree, then it is clear that 3 O cir(G) O 4, where cir(G) denotes the length of a longest cycle in G.
We prove that cir(G) = 3.
Suppose that cir(G) = 4.
Let C4 : v1 , v2 , v3 , v4 , v1 be a 4-cycle in G.
Since n Ou 5 and G is connected, there is a vertex x not on C4 such that x is adjacent to some vertex say, v1 of Then x, v1 , v2 , v4 , v4 is a path of length 4 in G and so diamD (G) Ou 4, which Santhakumaran and S.
Ullas Chandran is a contradiction.
Thus cir(G) = 3.
Also, if G contains two or more cycles, then it follows that diamD (G) Ou 4.
Hence G contains a unique triangle, say C3 : v1 , v2 , v3 , v1 .
Since n Ou 5, at least one vertex of C3 has degree at least 3.
there are two or more vertices of C3 having degree at least 3, then diamD (G) Ou 4, which is a contradiction.
Thus exactly one vertex of C3 has degree at least 3 and it follows that G = K1,nOe1 e.
This completes the proof.
Detour and Vertex Detour Hull Numbers and Addition of A Pendant Edge In this section we discuss how the detour hull number and the vertex detour hull number of a connected graph are affected by adding a pendant edge to G.
Let GA be a graph obtained from a connected graph G by adding a pendant edge uv, where u is not a vertex of G and v is a vertex of G.
Theorem 3.
If GA is a graph obtained from a connected graph G by adding a pendant edge uv at a vertex v of G, then dh (G) O dh (GA ) O dh (G) 1.
Proof.
Let S be a minimum detour hull set of G and let S A = S O .
We show that S A is a detour hull set of GA .
Let x OO V (GA ).
If x = u, then x OO S A .
So, assume that x OO V (G).
Then x OO ID [S]G for some k Ou 0.
Since ID
[S]G = ID
[S]GA for all A A A n Ou 0, we have x OO ID [S]G .
Also, since S OI S , we see that ID [S]G OI ID
[S A ]GA
A A
for all n Ou 0.
Hence x OO ID [S ]G .
This implies that S is a detour hull set of GA so that dh (GA ) O |S A | = |S| 1 = dh (G) 1.
For the lower bound, let S A be a minimum detour hull set of GA .
Then by Theorem 1.
1, u OO S A and v OO / S A .
Let S = (S Oe .
) O .
We prove that S is a detour hull set of G.
For this, first we claim that ID [S A ]GA Oe .
OI ID [S]G for all k Ou 0.
We use induction on k.
Since A S Oe .
OI S, the result is true for k = 0.
Let k = 1 and let x OO ID [S A ]GA Oe .
Then x 6= u.
If x OO S A , then x OO S OI ID [S]G .
If x OO / S A , then there exist y, z OO S A A such that x OO ID .
, .
G with x 6= y, z.
If y 6= u and z 6= u, then y, z OO S and so ID .
, .
G = ID .
, .
GA .
Thus x OO ID [S]G .
Now, let y = u or z = u, say z = u.
Since v is a cut vertex of GA , it follows that x OO ID .
, .
GA = ID .
, .
G and hence x OO ID [S]G .
Assume that the result is true for k = l.
Then ID [S A ]GA Oe.
OI ID [S]G .
l 1 A A Now, let x OO ID [S ]GA Oe .
If x OO ID [S ]GA , then by induction hypothesis, we have x OO ID
[S]G OI ID
[S]G .
If x OO
/ ID
[S A ]GA , then there exist y, z OO ID
[S A ]GA
such that x OO ID .
, .
GA with x 6= y, z.
If y 6= u and z 6= u, then it follows from induction hypothesis that y, z OO ID [S]G .
Also, since ID .
, .
GA = ID .
, .
G , we have x OO ID [S]G .
Let y = u or z = u, say z = u.
Then y 6= u and so by induction hypothesis, y OO ID [S]G .
Since v is a cut vertex of GA , it follows that x OO ID .
, .
GA = ID .
, .
G .
Also, since v OO S OI ID [S]G , it follows that x OO ID [S]G .
Hence the proof of the claim is complete by induction.
Now, since S A is a minimum detour hull set of GA , there is an integer r Ou 0 such that ID [S A ]GA = V (GA ) and it follows from the above claim that ID [S]G = V (G).
Thus S is a detour hull set of G so that dh (G) O |S| = |S A | = dh (GA ).
This completes the proof.
On the Detour and Vertex Detour Hull Numbers Remark 3.
The bounds for dh (GA ) in Theorem 3.
1 are sharp.
Let GA be the graph obtained from the graph G in Figure 3, by adding a pendant edge at one of its end vertices.
Then dh (GA ) = dh (G) = 2.
If GA is obtained from G by adding a pendant edge at one of its cut vertices, then dh (GA ) = dh (G) 1.
Figure 3.
Graph G with dh (GA ) = dh (G) 1 Theorem 3.
Let GA be a graph obtained from a connected graph G by adding a pendant edge uv at a vertex v of G.
Then dh (G) = dh (GA ) if and only if v is a vertex of some minimum detour hull set of G.
Proof.
First, assume that there is a minimum detour hull set S of G such that v OO S.
Let S A = (S Oe .
) O .
Then |S A | = |S|.
We show that S A is a detour hull set of k 1 A GA .
First, we claim that ID
[S]G OI ID
[S ]GA for all k Ou 0.
We prove this by using induction on k.
Let k = 0.
Let x OO S.
If x 6= v, then x OO S A OI ID [S A ]GA .
If x = v, then x OO ID .
, .
GA OI ID [S A ]GA , where y OO S such that y 6= v.
Thus S OI ID [S A ]GA .
l 1 A Assume the result for k = l.
Then ID
[S]G OI ID
[S ]GA .
Let x OO ID [S]G .
l 1 A l 2 A If x OO ID [S]G , then by induction hypothesis, x OO ID [S ]GA OI ID [S ]GA .
/ ID
[S]G , then there exist y, z OO ID [S]G such that x OO ID .
, .
G = ID .
, .
GA .
l 1 A l 2 A By induction hypothesis, we have y, z OO ID [S ]GA and so x OO ID [S ]GA .
Hence by k 1 A induction ID [S]G OI ID [S ]GA for all k Ou 0.
Now, since S is a detour hull set of G, there exists an integer r Ou 0 such that ID [S]G = V (G) and it follows from the r 1 A A above claim that ID [S ]GA = V (G ).
Thus S A is a detour hull set of G so that dh (GA ) O |S A | = |S| = dh (G).
The other inequality follows from Theorem 3.
Conversely, let dh (G) = dh (GA ).
Let S A be a minimum detour hull set of GA .
Then by Theorem 1.
3, u OO S A and v OO / S A .
Let S = (S A Oe .
) O .
Then, as in the proof of Theorem 3.
1, we can prove that S is a detour hull set of G.
Since |S| = |S A | = dh (GA ) = dh (G), we see that S is a minimum detour hull set of G and v OO S.
This completes the proof.
Theorem 3.
Let G be a connected graph and let x be any vertex in G.
If GA is a graph obtained from G by adding a pendant edge xu, then dhx (GA ) = dhx (G) 1.
Proof.
Let S be a minimum x-detour hull set of G and let S A = S O .
Then, as in Theorem 3.
1, it is straight forward to verify that ID [S]xG OI ID [S A ]xGA for all n Ou 0.
Since S is an x-detour hull set of G, there is an integer r Ou 0 such that Santhakumaran and S.
Ullas Chandran [S]xG = V (G) Oe .
and it is clear that ID [S A ]xGA = V (GA ) Oe .
Hence S A is an A A x-detour hull set of G so that dhx (G ) O |S A | = dhx (G) 1.
Now, suppose that dhx (GA ) < dhx (G) 1.
Let S A be a minimum x-detour hull set of GA .
Then, by Theorem 1.
3, u OO S A .
Let S = S A Oe .
Then, as in Theorem 3.
1, it is straight forward to prove that ID [S A ]xGA Oe.
OI ID [S]xG for all n Ou 0.
Since S A is an x-detour hull set of G , there is an integer r Ou 0 such that ID [S A ]xGA = V (GA ) Oe .
Hence ID [S]G = V (G) Oe .
Thus S is an x-detour hull set of G so that dhx (G) O |S| = dhx (GA ) Oe 1, which is a contradiction to dhx (GA ) < dhx (G) 1.
Hence the result Theorem 3.
Let GA be a graph obtained from a connected graph G by adding a pendant edge uv at a vertex v of G.
Then dhu (GA ) = dhv (G).
Proof.
Let S be a minimum v-detour hull set of G.
Then v OO / S.
As in Theorem 3.
it is straight forward to prove that ID [S]vG OI ID [S]uGA for all n Ou 0.
Since S is a vr detour hull set of G, there is an integer r Ou 0 such that ID [S]vG = V (G)Oe.
Now, since v OO ID .
uG for any z OO S, it follows that ID [S]uG = V (GA )Oe.
Hence S is a udetour hull set of GA so that dhu (GA ) O |S| = dhv (G).
For the other inequality, let T be a minimum u-detour hull set of GA .
Then u OO / T and by Theorem 1.
, v OO / T.
As in Theorem 3.
1, it is straight forward to prove that ID [T ]uGA Oe .
OI ID [T ]vG for all n Ou 0.
Since T is a u-detour hull set of GA , there is an integer r Ou 0 such [T ]vG = V (G) Oe .
and T that ID [T ]uGA = V (GA ) Oe .
Hence it follows that ID is a v-detour hull set of G.
Thus dhv (G) O |T | = dhu (GA ).
This completes the Theorem 3.
Let G be a connected graph and x any vertex of G.
Let GA be a graph obtained from G by adding a pendant edge uv at a vertex v 6= x of G.
Then dhx (G) O dhx (GA ) O dhx (G) 1.
Proof.
The proof is similar to Theorem 3.
Theorem 3.
Let G be a connected graph and x any vertex of G.
Let G be a graph obtained from G by adding a pendant edge uv at a vertex v 6= x of G.
Then dhx (G) = dhx (GA ) if and only if v belongs to some minimum x-detour hull set of Proof.
The proof is similar to Theorem 3.
On the Detour and Vertex Detour Hull Numbers References