A Study on Detour Number

 

S. Jeelani Begum^1*, B. Ranjitha², L. Eswaramma³, S. GouseMohiddin⁴

 

ABSTRACT:

A path of maximum length in a connected graph G(V, E) is called a detour path between u and v, and is denoted by ∂(u, v). For any vertex u in a connected graph G, we define the length of a detour path in a graph G is called the detour number of G, and is denoted by ∂(G). i.e. ∂(G) = max { ∂(u): u ∈V(G) }.  In this paper we study on several bounds on graph-theoretic parameters in terms of the detour number. 

 

 

 

INTRODUCTION:

A graph is said to be connected if every distinct pair of its vertices are joined by a path. Let G be a connected graph. For any two vertices u and v of G, the distance between u and v is defined to be the length of a shortest path between u and v and is denoted by d(u, v). It is easy to see that the distance function d is metric on V(G). Ore [5] Kapoor et.al. [4], Chartrand et.al. [1,2&3], have obtained some results regarding the study on detour concepts.

 

The detour radius of G, and is denoted by rad*(G) = r∂(G),  is defined as the number and C∂(G) = {v ∈V; ∂(v) = r∂(G) } is called the detour centre of G. The detour diameter of G, and is denoted by diam*(G), is defined as the number. A block of a graph G is a maximal connected subgraph of G containing no cutvertices. A graph with a hamiltonian path is called traceable. A graph G is detour-connected if for every two distinct vertices u and v of G, there exists a detour path with u and v as end vertices.

If G is detour-connected and traceable graph, then every pair of vertices in G are joined by a hamiltonian path. Such graphs are called hamiltonian- connected.

 

Observation 1:

if G is any graph on p vertices having a hamiltonian path, then ∂(G) = p - 1.

 

Observation 2:

(i) For any connected graph G having p ≥ 3 vertices, ∂(G) ≥ 2;

(ii) ∂(G) = 2 if and only if either G is a triangle or star, and

(iii) ∂(G) = p - 1, then either G has hamiltonian path or G is a complete graph of order p.

 

MAIN RESULTS:

Theorem 1:

If G is a connected graph of order p having minimum degree r, then 

∂(G) ≥ min { p - 1, 2r }.

 

Proof: If ∂(G) = p - 1, then the result follows. Thus we assume

∂(G) < min { p - 1, 2r }. Let P be a path of length ∂(G) = ∂ whose vertices are successively v0, v1, v2 ,…, v∂. The subgraph G' induced by the set of vertices of P cannot contain a cycle having all vertices G'; otherwise, there would be necessarily exist a point v not in G' adjacent with some vertex vi in G' producing a path of length ∂+1. Similarly, v0 and v∂ are adjacent only to vertices of G' but not each other. By hypothesis, the sum of degrees of v0 and v∂ is at least 2r. Since ∂(G) < 2r, there must exist vertices vi-1 and vi in G, where vi is adjacent to v0 and vi-1 and also it is adjacent to v∂. This implies the existence the cycle, which contains all the vertices of G'. But it is seen that this is impossible. Therefore, ∂(G) ≥ min { p - 1, 2r }.

 

Since every n-connected graph has minimum degree ≥ n. The following result is immediate.

 

Proposition 2:

If G is an n-connected graph of order p then ∂(G) ≥ min { p -1, 2n}.

 

Theorem 3:

If G is a connected graph, then C∂(G) lies in a block of G.

Proof:

Let G be a connected graph with detour number ∂(G) = ∂ and assume that C∂(G) fails to lie in a block of G. Then G has cutvertex v with the property that at least two components G1 and G2 of the graph G - v contains vertices of C∂(G). Let P be a path of length ∂(v) having an endvertex at v. Since v is a cutvertex at least one of the subgraphs G1 and G2, say G2, contains no vertices of P. Let u be a vertex of G2 belonging to C∂(G). If Q is a path having end vertices at u and v, then the paths P and Q determine a path having length exceeding ∂(v), i.e., ∂(u) > ∂(v). This, contradicts the fact that u belongs to C∂(G) is contained in a block of G.        

 

Proposition 4:

The detour centre of a tree consists of one vertex or two adjacent vertices.

 

Proof:

It is an elementary observation that for a tree, the detour number equals to its diameter, every detour path is a diametrical path, and the detour centre coincides with the centre. Such is not the case in graphs other than trees.For the graph given in Figure 1, { C1, C2, C3 } constitutes the centre and {d1, d2 } the detour centre.

 

 

Figure 1

Theorem 5:

A graph G is detour-connected if and only if G is hamiltonian- connected.

 

Proof:

It is obvious that every hamiltonian-connected is detour-connected. For the converse, let G be a detour-connected graph. If G has only two vertices, then G is hamiltonian-connected. If G has more than two vertices then let u and v   be any two adjacent vertices of G. Since G is detour-connected, there exists a detour path P having u and v  as end vertices. We now claim that P contains all the vertices of G implying G is traceable and therefore, G is hamiltonian-connected. To see this consider the cycle C determined by the path P and the edge uv. If C does not contain all vertices of G, then since G is connected, there exists a vertex w not on C but adjacent with a vertices of C. This produces a path of length ≥ p + 1. This is a contradiction. Thus C and therefore P contain all vertices of G.

 

The proof of Theorem 5 also provides the following corollary.

 

Corollary 6:

If G is detour-connected graph with p ≥ 3 vertices then G is hamiltonian.

 

ACKNOWLEDGEMENT:

The corresponding author acknowledge Department of Science and Technology, Government of India for financial support wide reference no: No.SR/WOS-A/MS-07/2014 (G) under women scientist scheme to carry out this work.

 

REFERENCES:

1.     Chartrand, Gary, Henry Escuadro, and Ping Zhang. "Detour distance in graphs." Journal of Combinatorial Mathematics and Combinatorial Computing53 (2005): 75-94.

2.     Chartrand, Gary, Garry L.Johns, and Ping Zhang."On the detour number and geodetic number of a graph."ArsCombinatoria 72 (2004): 3-15.

3.     Chartrand, Gary, et al. "Detour domination in graphs." Ars Combinatoria 71 (2004): 149-160.

4.     Kapoor. S. F., Kronk.H.V., Lick.D.R., On detours in graphs ,Canad. Math. Bull., 11 (1968), pp. 195-201.

5.     Ore, O. "Hamiltonian connected graph." J. Math. PuresAppli 42 (1963): 121-127.

 

 

Accepted on 09.09.2017      ©A&V Publications All right reserved