Original Article

, Volume: 15( 1)

• View PDF
• Download PDF

D-Radius and D-Diameter of Some Families of Graphs

*Correspondence:

Reddy Babu D Department of Mathematics(PPMat089), Rayalaseema University, Kurnool, India, Tel: +919441752543; E-mail: reddybabu17@gmail.com

Abstract

The D-distance between vertices of a graph is obtained by considering the path lengths and as well as the degrees of vertices present on the path. In this article, we study the D-radius and D-diameter of some families of graphs with respect to D-distance. 2000 Mathematics Subject Classification: 05C12.

Keywords

D-distance; D-radius; D-diameter

Introduction

By a graph G=(V, E), we mean a finite undirected graph without loops and multiple edges. The concept of distance is one of the important concepts in study of graphs. It is used in isomorphism testing, graph operations, Hamilton city problems, extremal problems on connectivity and diameter, convexity in graphs etc. Distance is the basis of many concepts of symmetry in graphs [1].

In an earlier article authors introduced the concept of D-distance [2], by considering not only path length between vertices, but also the degrees of all vertices present in a path while defining the D-distance.

Preliminaries

Throughout this article, by a graph G(V, E) or simply G, we mean a non-trivial, finite, undirected graph without multiple edges and loops. Further all graphs we consider are connected [3].

Definition 2.1: If u, v are vertices of a connected graph G the D-length P of a u-v path S is defined as l(s)=d(u, v)+deg(u)+deg(v)+ deg(w) where sum runs over all intermediate vertices w of s.

Definition 2.2: (D-distance). The D − distance d^D (u,v) between two vertices u,v of a connected graph G is defined as are distinct and where the minimum is taken over all u − v paths s in G .

Definition 2.3: The D-eccentricity of any vertex v, e^D (v) , is defined as the maximum distance from v to any other vertex,

Definition 2.4: Any vertex u for which is called D eccentric vertex of v . Further, a vertex u is said to be D eccentric vertex of G if it is the D − eccentric vertex of some vertex.

Definition 2.5: The D-radius, denoted by r^D (G) , is the minimum D-eccentricity among all vertices of G i.e., Similarly the D-diameter, d^D (G) is the maximum D-eccentricity among all vertices of G.

Definition 2.6: The D-center of G, C^D (G) , is the sub graph induced by the set of all vertices of minimum D− eccentricity. A graph is called D-self-centered if C^D(G) = G or equivalently r^D (G) = d^D(G). Similarly, the set of all vertices of maximum D-eccentricity is the D-periphery of G.

D-radius and D-diameter of families of graphs

There are some graphs for which D-radius and D-diameter are same, i.e., they are D-self-centered.

Theorem 3.1: For Complete graph, , K_n on n vertices

Proof: In complete graph K_n , degree of each vertex is n − 1.Thus D-distance between any two vertices is 1+ n-1+ n-1= 2n-1. Thus D-eccentricity of every vertex is 2n -1. Hence D-radius and D-diameter of K_n equal and is equal to 2n -1.

Theorem 3.2: For cycle graph, C_n ,with n vertices we have

Proof: In cycle graph C_n, degree of each vertex is 2. the D-distance between the vertices is given below. We will consider even and odd cases separately.

Case 1: When n is even, the D-distance in C_n are as below.

Table 1. D-eccentricity of every vertex is . Hence the D- radius and D-diameter is same, if n is even.

Case 2: When n is odd, the D-distance in C_n are as below

Table 2. D-eccentricities of each vertex is , if n is odd.

Hence D-radius and D-diameter is same. Thus

Next, we calculate D-radius and D-diameter of some families of graphs

Theorem 3.3: for complete biaparted graph we have

Proof: Without loss of generality assume that (m ≥ n) . N complete biparted graph K_m,n degree of the vertices v₁,v₂,v₃....v_m is n and degree u₁,u₂,u₃....u_n of the vertices m . Thus

if if

Therefore, and Hence the D-radius of K_m,n is m + 2(n +1) and D-diameter of K_m,n is n + 2(m + 1).

Theorem 3.4: For star graph,

Proof: In star graph, st_n,1 the degree of central vertex is n and degree of remaining vertices is 1. The D-distance from central vertex to other vertices is n + 2 and the D-distance between all other vertices is n + 4 Therefore the minimum Deccentricity is n + 2 and the maximum D-eccentricity is n + 4 Hence the D-radius of st_n,1 is n + 2 of n + 4

Theorem 3.4: For path graph P_n , on n vertices (n ≥ 3) we have and Further

Proof: In path graph P_n , degree of end vertices is 1 and remaining vertices of degree is 2.

For Thus the D-eccentricity of each vertex is 3. Hence the D-radius and D-diameter of P₂ are same and equal to 3.

Next consider path graph with n ≥ 3. we can consider even and odd cases separately, in this case the D-distance between vertices are as given below.

Case 1: When n is odd, the D-distance in P_n are as below

Table 3. D-eccentricities are

Thus the maximum D-eccentricity of P_n is 3n - 3 and minimum D-eccentricity is Hence the D-radius is and the D-diameter is 3n - 3 if n is odd.

Case 2: When n is even, the D-distance in P_n are as below

Table 4. D-eccentricities are

Thus the maximum D-eccentricity of P_n is 3n - 3 and minimum D-eccentricity is Hence the D-radius is and the D-diameter is 3n - 3 if n is even.

Theorem 3.5: For wheel graph, W_n,1 , with n + 1 vertices we have and for n ≥ 6. Further we have

Proof: For Thus the D-eccentricity of every vertex is 7. Hence the D-radius and Ddiameter of W_3,1 is 7 ( and hence W_3,1 is self-centered ).

For if v_i is central vertex and or 11, if v_i is not central vertex. Thus the Deccentricity central vertex is 8 and the D-eccentricity of other vertices is 11. hence the D-radius of W_4,1 is 8 and Ddiameter of W_4,1 is 11.

For if v_i is central vertex and or 11, if i v is not central vertex. Thus the Deccentricity central vertex is 9 and the D-eccentricity of other vertices is 11. hence the D-radius of W_5,1 is 9 and Ddiameter of W_5,1 is 11.

In wheel graph W_n,1 degree of central vertex is n and degree of remaining vertices is 3. Thus D-eccentricity of central vertex is n + 4 and D-eccentricity of remaining vertices is n + 8 for n ≥ 6. Thus the D-radius of W_n,1 is n + 4 and Ddiameter of W_n,1 is n + 8 for n ≥ 6.

References

1. Buckley F, Harary F. Distance in Graphs, Addison-Wesley. Longman. 1990.
2. Reddy Babu D, Varma PLN. 130. Some inequalities on D-distances. Bull Math Stat Res. 2013;2:53-8.
3. Reddy Babu D, Varma PLN. A note on radius and diameter of a graph w.r.t, D-distance. Int J chem sci. 2016;14(2):1725-29.