ddM- Distance In Graphs

ddM- Distance In Graphs

– Distance In Graphs

K. John Bosco

Assistant Professor, Department of Mathematics, St.

Judes College Thoothoor,

Sathija J Prathisa S K

Research Scholar (Reg.No: 23113232092005), Department of Mathematics, St. Judes College Thoothoor,

Afflicated to Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli 627012, Tamilnadu, India.

ABSTRACT

For two vertices , of a graph G, the usual distance d (u, v), is the length of the shortest path between u and v. In

this paper we introduced the concept of – distance by

considering the degrees of various vertices presented in the

path, in addition to the length of the path. We study some properties with this new distance. We define the eccentricities

of vertices, radius and diameter of G with respect to the –

distance. First we prove that the new distance is a metric on

the set of vertices of G. We compare the usual, geodesic and

– distances of two vertices , of V.

KEYWORDS

Geodesic distance, – distance, – Eccentricity, – Radius and – Diameter.

1. INTRODUCTION

   introduced the concept of – distance. In some of these

   distances only the lengths of various paths were considered.

   We introduce the concept of mean – distance in some

   graphs G.

2. – DISTANCEINGRAPHS DEFINITION 2.1

Let u, v be two vertices of a connected graph G.

Then the mean – length of a u – v path defined as ddM

(u,v) = d(u, v) + deg (u) + deg (v) + deg() + deg () or

2

deg() + deg ()

, where d (u, v) is the shortest distance

2

between the vertices u and v. The – distance between two vertices u and v is defined as the – length of a u – v

path.

By a graph G, we mean a non-trivial finite undirected connected graph without multiple edges and loops. Following standard notations (for any unexplained notation and terminology we refer [2]) V(G) or V is the vertex set of G and

DEFINITION 2.2

The ddM – eccentricity of any vertex v ,

(), is

E(G) or E is the edge set of G = G(V, E). Let , be two vertices of G. The standard or usual distance (, ) between

is the length of the shortest path in G.

Chartrandel al [3] introduced the concept of detour distance

in graphs as follows: For two vertices , in a graph G,the detour distance (, ) is defined as the length of the longest path in G. In this article we introduce a new distance, which we call as – distance between any two

vertices of a graph G, and study some of its properties. This

distance is significantly different from other distances. In some of the earlier distances, only path length was considered. Here we, in addition, consider the degree of

vertices present in a path while defining its length. Using this length we define the -distance.

Chartand et al introduced the concept of detour distance by

considering the length of the longest path between u and v. Kathiresan et al [4] introduced the concept of superior distance and signal distance. Goldern Ebenezer et al [13]

defined as the maximum distance from v to any other vertex,

i.e., () = { (, ): , ()}

DEFINITION 2.3

Any vertex for which(, ) = () is called

ddM – eccentric vertex of v. Further, a vertex u is said to be ddM

– eccentric vertex of G if it is the ddM – eccentric vertex of some vertex.

DEFINITION 2.4

The ddM – radius, denoted by (), is the minimum

ddM – eccentricity among all vertices of G i.e., () =

{ (): ()}. Similarly the ddM – diameter, ddM

(G), is the maximum ddM – eccentricity among all vertices of G.

Suppose that u = w.Then ddM (u,w) = 0.

Therefore ddpM (u,w) + ddpM (w,v) = 0 + l (Q) +deg (w) + deg(v)

deg()+ deg ()

+

2

DEFINITION 2.5

A graph is called self centered if radius is same as

diameter, i.e., = .

THEOREM 2.6

If G is any connected graph, then the ddpM – distance is a metric on the set of vertices of G.

PROOF:

Let G be a connected graph and u, v V(G). Then it is clear by definition that ddM (u, v) 0 and ddM (u, v) = 0 which implies u = v. It is obvious that ddM (u, v) = ddM (v, u). It can be proved that the distance ddM satisfies the triangle inequality.

Case (i):

Let u, v, w V(G). Let P and Q be u – w and w – v

shortest paths of shortest lengths l(P) and l(Q) respectively in

1. Then ddM (u,w) = l (P) + deg (u) + deg (w) +

   deg()+ deg ()

   = l (PQ) + deg (u) + deg (v) + deg()+ deg ().

   2

   ddM (u,w) + ddM (w, v) = ddM (u,v).

   Subcase (ii):

   Suppose that v = w. Proof is similar to subcase (i).

   Thus the triangular inequalities hold and hence ddM is a metric on the vertex set.

   COROLLARY 2.7

   For any three vertices u, v, w of a graph G, ddM (u,v)

   ddM (u,w) + ddM (w,v) 2 deg (w)

   PROOF:

   Let G be a connected graph.

   ddM (u,w) + ddM (w,v) = l (PQ) + , = PQ () + deg (w) + , = PQ () + deg (w) + , = PQ ()

   ddM (u, v) + 2 deg (w).

   ddM (u,w) + ddM (w,v) ddM (u,v) + 2 deg (w).

   and ddM (w, v) = l (Q) + deg (w) + deg (v) +

   2

   deg()+ deg ()

   2

   . Let R = PQ be the u v shortest path

   Hence ddM

   (u,v) ddM

   (u,w) + ddM

   (w,v) – 2 deg (w).

   obtained by joining P and Q at w of length greater than one.

   Then ddM (u,w) + ddM (w,v) = [ l (P) + deg (u) + deg (w) +

   deg()+ deg ()

   ] + [ l (Q) + deg (w) + deg (v) +

   2

   deg()+ deg ()

   ]

   2

   PREPOSITION 2.8

   If G is a connected graph with two distinct vertices u, v

   = l (PQ) + deg (u) + deg (v) + 2 deg (w) +

   are adjacent then ddM (u, v) 4(n 1).

   deg()+ deg ()

   deg()+ deg ()

   2

   +

   2

   deg()+ deg ()

   PROOF:

   = l (R) + deg (u) + deg (v) + 2 deg (w) + +

   2

   deg()+ deg ()

   Let u and v be two adjacent vertices. This implies that

   d(u, v) n – 1. Bydefinition, ddM (u,v) = d (u,v) + deg (u) +

   2

   deg (v) + deg ( )+ deg ( ) deg (u) + deg (v) + (n – 1) +

   > l (R) + deg (u) + deg (v) + deg ( )+ deg ( ) +

   2

   deg()+ deg ()

   deg ( ) + deg ( )

   2 . Since d(u,v) n – 1, deg (v) n – 1 for any

   2

   2 vertices u and v. Hence ddM (u,v) 4 (n – 1).

   = ddM (u,v).

   Therefore ddM (u,w) + ddM (w, v) > ddM (u, v).

   Case (ii):

   Suppose R = PQ be the u – v shortest path of length one.Then we take a vertex w other than u and v and so we

   have either u = w or v = w.

   Subcase (i):

   THEOREM 2.9

   For every tree u,v T, ddM (u,v) d (u,v).

   PROOF:

   In a tree ddM (u,v) = d(u,v). We know that ddM (u,v) =

   d(u,v) + deg (u) + deg (v) + deg()+ deg ()

   2

   This implies that ddM (u,v) > d(u,v).

   The following results are immediate for complete graph.

   THEOREM 2.10

   In path graph Pn, the product mean of any vertex,

   3 is given below The diameter =+.

   The radius , If n is odd then (, ) = (1) + 5.

   2

   If n is even then (, ) = () + 5.

   2

   THEOREM 2.11

   1. For a compete grph Kn, ddM (u,v) = 3n – 2 for every u,v Kn.

1. For a complete bipartite graph G = Km,n ,m =

   n and = V(G), (, ) = 3 + 2

   u, v .

2. For a star graph G = K1,n, if n is odd,

+1

CONCLUSION:

Many researchers are concentrating various distance

concepts in graphs. In this paper we have studied about

– distance in graphs. Then we have defined ddM – eccentricity,

ddM – radius and ddM diameter. Many results have been found.

REFERENCE

[1] F. Buckley and F. Harary, Distance in graphs, Addison – Wesley, Longman,1990.

[2] G. Chartrand, H. Escuadro and P. Zhang, Detour distance in graphs, J. Combin. Comput, 53 (2005) 75 – 94.

[3] G. Chartrand and P. Zang, Introduction to Graph Theory,TataMcGraw- Hill, (2006).

[4] K. M. Kathiresan and G. Marimuthu, Superior distance in graphs, J. Combin. Comput., 61 (2007) 73 – 80.

[5] K. M. Kathiresan and R. Sumathi, A study on signal distance in graphs, Algebra, graph theory and their applications, Narosa publishing house Pvt. Ltd (2010) 50 – 54.

[6] D. Reddy Babu and L. N. Varma, P., D – Distance in graphs, Golden Research Thoughts, 9 (2013) 2231 – 5063.

[7] Galeana – SnchezH,Xueliang Li, 1998, Semi kernals and (k,l)- kernals in digraphs, SIAMJ. DiscreteMath, Vol. 11, No. 2,340-346.

[8] Haynes T. W, Hedetniemi S.T, Slater P. J, 1998, Fundamentals of Dominationin Graphs, Marcel Dekker, Inc.NewYork.

[9] Haynes T.W, Hedetniemi S.T, Slater P.J, 1998, Domination in Graphs: Advanced Topics,Marcel Dekker,NewYork.

[10] Lee C, 1994, On the Domination Number of a Digraph, Ph.D. Dissertation, Michigan StateUniversity.

[11] Woch A, 2012, On 2 dominatingkernelsingraphs,

Austr..J.Combin.53: 273 – 284.

2

(, ) = 3 (

) + 1 v V(G)

if n is even,

[12] Woch A,WochI,2009,On(k;l)- kernelsin thecoronaofdigraphs, Int.

J.PureAppl.Math.53 (4):571-582.

[13] T. Jackulin, J. Goldern Ebenezer Jebamani, D. Premlatha, 2022, d distance in graphs, Journal of Xian Shiyou University, Natural Science Edition, Volume 18.

2

(, ) = 3 ( ) + 3 v V(G)

[14] K. John Bosco, Sathija J Prathisa S K, 2023,

– distance in graphs,

Journal of Emerging Technologies and Innovative Research, IJ

Publication, Volume 10, Issue 5.

PROOF:

Above results are obvious by definitions.

COROLLARY 2.12

1. Complete graph Kn is self centered.

2. Complete bipartite graph Km,n (m = n), is self centered.

3. Star graph K(1,n), is self centered.

OBSERVATION 2.13

For any connected graph G, if u and v are end vertices of G and d (u,v) n 1 then ddM (u,v) 4(n 1).