Advances in Pure Mathematics
Vol.08 No.06(2018), Article ID:85362,11 pages
10.4236/apm.2018.86032

Modified Generalized Degree Distance of Some Graph Operations

Shengmei Lv

School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China

Copyright © 2018 by author and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: May 3, 2018; Accepted: June 17, 2018; Published: June 20, 2018

ABSTRACT

The modified generality degree distance, is defined as: H λ * ( G ) = { u , v } V ( G ) d λ ( u , v ) ( d G ( u ) d G ( v ) ) , which is a modification of the generality degree distance. In this paper, we give some computing formulas of the modified generality degree distance of some graph operations, such as, composition, join, etc.

Keywords:

Degree Distance, Modified Generalized Degree Distance, Graph Operations

1. Introduction

Throughout this paper all graphs considered are finite and simple graphs. Let G be such a graph with vertex set V ( G ) and edge set E ( G ) , and denoted by n and m the values of | V ( G ) | and | E ( G ) | , respectively. For vertices u , v V ( G ) , the distance between u and v in G, denoted by d G ( u , v ) , is the length of a shortest ( u , v ) -path in G, and let d G ( v ) be the degree of a vertex v V ( G ) . The complement of G, denoted by G ¯ , is the graph with vertex set V ( G ) , in which two distinct vertices are adjacent if and only if they are not adjacent in G, and denoted by m ¯ the value of | E ( G ¯ ) | . We use C n , P n and K n to denote the cycle, path and complete graph on n vertices, respectively. Other terminology and notation will be introduced where it is needed or can be found in [1] .

A Topological index of a graph is a real number related to the graph; it does not depend on labeling or pictorial representation of a graph. In chemistry, topological index is used for modeling physicochemical, pharmacologic, biological and other properties of chemical compounds [2] . One of the oldest and well-studied distance-based graph invariants is the Wiener number W ( G ) , also termed as Wiener index in chemical or mathematical chemistry literature, which is defined [3] as the sum of distances over all unordered vertex pairs in G, namely,

W ( G ) = { u , v } V ( G ) d G ( u , v ) .

Dobrynin and Kochetova [4] and Gutman [5] introduced a new graph invariant with the name degree distance or Schultz molecular topological index, which is defined as follows:

D D ( G ) = { u , v } V ( G ) ( d G ( u ) + d G ( v ) ) d G ( u , v ) .

In [6] , Gutman and Klavzar defined product-degree distance as follow:

D D ( G ) = { u , v } V ( G ) ( d G ( u ) d G ( v ) ) d G ( u , v ) .

Note that the degree distance and product-degree distance are degree-weight versions of the Wiener index. We encourage the interested readers to consult [7] [8] [9] for Wiener index. In [4] [10] [11] [12] [13] [14] , there are more conclusions for degree distance, which shows that the research of degree distance is a hot topic. In [15] , Sagan et al. computed some exact formulae for the Wiener polynomial of various graph operations containing Cartesian product, composition, join, disjunction and symmetric difference of graphs, whose concepts will be presented in later part. In [16] , Hamzeh et al. consider the generalized degree distances of some graph operations. The generalized degree distance of a graph is defined as follow [17] :

H λ ( G ) = { u , v } V ( G ) d λ ( u , v ) ( d G ( u ) + d G ( v ) ) . (1)

For a real number λ , the modified generalized degree distance, denoted by H λ * ( G ) , is also defined in [17] :

H λ * ( G ) = { u , v } V ( G ) d λ ( u , v ) ( d G ( u ) d G ( v ) ) . (2)

If λ = 0 , H λ ( G ) = 4 m and H λ * ( G ) = 4 m 2 . When λ = 1 , H λ ( G ) = D D ( G ) and H λ * ( G ) = D D * ( G ) , which implies that the generalized degree distance is equal to the degree distance (or Schultz index), and the modified generalized degree distance is equal to the product-degree distance. Therefore the study of this new topological index is important and we try to obtain some new results related to this topological index.

In this paper, we show that the explicit formulas for H λ * ( G ) of some graph operations containing the composition, join, disjunction and symmetric difference of graphs, and we apply the results to compute the modified generality degree distance of some special graphs.

Next, we introduce four types of graph operations:

The join G = G 1 + G 2 of graphs G 1 and G 2 with disjoint vertex sets V 1 , V 2 and edge sets E 1 , E 2 is the graph union G 1 G 2 together with all the edges joining V 1 and V 2 .

The composition G = G 1 [ G 2 ] of graphs G 1 and G 2 with disjoint vertex sets V 1 and V 2 and edge sets E 1 and E 2 is the graph with vertex set V 1 × V 2 and u = ( u 1 , v 1 ) is adjacent with v = ( u 2 , v 2 ) whenever ( u 1 is adjacent with u 2 ) or ( u 1 = u 2 and v 1 is adjacent with v 2 ), see [18] .

The disjunction G H of graphs G and H is the graph with vertex set V ( G ) × V ( H ) and ( u 1 , v 1 ) is adjacent with ( u 2 , v 2 ) whenever u 1 u 2 E ( G ) or v 1 v 2 E ( H ) .

The symmetric difference G H of two graphs G and H is the graph with vertex set V ( G ) × V ( H ) and E ( G H ) = { ( u 1 , u 2 ) ( v 1 , v 2 ) | u 1 v 1 E ( G ) or u 2 v 2 E ( H ) butnotboth } .

In the final of this section, we present several well-known indices: the first Zagreb index M 1 ( G ) and the second Zagreb index M 2 ( G ) [19] , the first Zagreb conindex M ¯ 1 ( G ) and the second Zagreb coindex M ¯ 2 ( G ) [20] , which will be used in our results.

M 1 ( G ) = u V ( G ) d G ( u ) 2 , M ¯ 1 ( G ) = u v E ( G ) ( d G ( u ) + d G ( v ) ) .

M 2 ( G ) = u v E ( G ) ( d G ( u ) d G ( v ) ) , M ¯ 2 ( G ) = u v E ( G ) ( d G ( u ) d G ( v ) ) .

In fact, M 1 ( G ) can be also expressed as a sum over edges of G,

M 1 ( G ) = u v E ( G ) ( d G ( u ) + d G ( v ) ) .

2. Main Results

The purpose of this section is to compute the modified generalized degree distance for four graph operations. We begin with the following crucial lemma related to distance properties of some graph operations.

Lemma 2.1. [18] [21] Let G and H be two graphs, then we have:

1) | V ( G H ) | = | V ( G [ H ] ) | = | V ( G H ) | = | V ( G ) | | V ( H ) | ,

| E ( G H ) | = | E ( G ) | | V ( H ) | 2 + | E ( H ) | | V ( G ) | 2 2 | E ( G ) | | E ( H ) | ,

| E ( G + H ) | = | E ( G ) | + | E ( H ) | + | V ( G ) | | V ( H ) | ,

| E ( G H ) | = | E ( G ) | | V ( H ) | 2 + | E ( H ) | | V ( G ) | 2 4 | E ( G ) | | E ( H ) | ,

| E ( G [ H ] ) | = | E ( G ) | | V ( H ) | 2 + | E ( H ) | | V ( G ) | .

2) The join, composition, disjunction and symmetric difference of graphs are associative and all of them are commutative except from composition.

3) d G + H ( u , v ) = ( 0 u = v 1 u v E ( G ) or u v E ( H ) or ( u V ( G ) & V V ( H ) ) 2 otherwise ,

4) d G [ H ] ( ( a , b ) , ( c , d ) ) = ( d G ( a , c ) a c 0 a = c & b = d 1 a = c & b d E ( H ) 2 a = c & b d E ( H ) ,

5) d G H ( ( a , b ) , ( c , d ) ) = ( 0 a = c & b = d 1 a c E ( G ) or b d E ( H ) 2 otherwise ,

6) d G H ( ( a , b ) , ( c , d ) ) = ( 0 a = c & b = d 1 a c E ( G ) or b d E ( H ) but not both 2 otherwise ,

7) d G + H ( a ) = { d G ( a ) + | V ( H ) | a V ( G ) d H ( a ) + | V ( G ) | a V ( H ) ,

8) d G [ H ] ( ( a , b ) ) = | V ( H ) | d G ( a ) + d H ( b ) ,

9) d G H ( ( a , b ) ) = | V ( H ) | d G ( a ) + | V ( G ) | d H ( b ) 2 d G ( a ) d H ( b ) ,

10) d G H ( ( a , b ) ) = | V ( H ) | d G ( a ) + | V ( G ) | d H ( b ) d G ( a ) d H ( b ) .

Proof. The parts 1) - 5) are consequence of definitions and some well-known results of the book of Imrich and Klavzar [18] . For the proof of 6) - 10) we refer to [21] .

For a given graph G i , we denote n i and m i by the number of vertices and edges, respectively. Then we can obtain the modified generalized degree distance of the join graph G 1 + G 2 as following:

Theorem 2.1. Let G 1 and G 2 be two graphs. Then

H λ * ( G 1 + G 2 ) = 2 λ ( n 2 M ¯ 1 ( G 1 ) + n 1 M ¯ 1 ( G 2 ) + M ¯ 2 ( G 1 ) + M ¯ 2 ( G 2 ) ) + 2 λ ( n 2 2 m ¯ 1 + n 1 2 m ¯ 2 ) + n 2 M 1 ( G 1 ) + n 1 M 1 ( G 2 ) + M 2 ( G 1 ) + M 2 ( G 2 ) + 4 m 1 m 2 + n 1 n 2 ( 2 m 1 + n 1 n 2 + 2 m 2 ) + n 2 2 m 1 + n 1 2 m 2 .

Proof. In the graph G 1 + G 2 , we can partition the set of pairs of vertices of G 1 + G 2 into three subsets A 1 , A 2 and A 3 . In A 1 , we collect all pairs of vertices u and v such that u is in G 1 and v is in G 2 . Hence, they are adjacent in G 1 + G 2 . The sets A 2 and A 3 are the set of pairs of vertices u and v which are in G 1 and G 2 , respectively. Therefore, we can partition the sum in the formula of H λ * ( G 1 + G 2 ) into three sums S i such that S i is over A i for i = 1 , 2 , 3 . By 3) and 7) of Lemma 2.1, we have

S 1 * = u V ( G 1 ) v V ( G 2 ) d G 1 + G 2 λ ( u , v ) ( ( d G 1 ( u ) + n 2 ) ( d G 2 ( v ) + n 1 ) ) = 4 m 1 m 2 + n 2 n 2 ( 2 m 1 + n 1 n 2 + 2 m 2 ) .

S 2 * = { u , v } V ( G 1 ) d G 1 + G 2 λ ( u , v ) ( ( d G 1 ( u ) + n 2 ) ( d G 1 ( v ) + n 2 ) ) = u v E ( G 1 ) ( ( d G 1 ( u ) + n 2 ) ( d G 1 ( v ) + n 2 ) ) + u v E ( G 1 ) 2 λ ( ( d G 1 ( u ) + n 2 ) ( d G 1 ( v ) + n 2 ) ) = 2 λ ( M ¯ 2 ( G 1 ) + n 2 M ¯ 1 ( G 1 ) + n 2 2 m ¯ 1 ) + M 2 ( G 1 ) + n 2 M 1 ( G 1 ) + n 2 2 m 1 .

S 3 * = { u , v } V ( G 2 ) d G 1 + G 2 λ ( u , v ) ( ( d G 2 ( u ) + n 1 ) ( d G 2 ( v ) + n 1 ) ) = u v E ( G 2 ) ( ( d G 2 ( u ) + n 1 ) ( d G 2 ( v ) + n 1 ) ) + u v E ( G 2 ) 2 λ ( ( d G 2 ( u ) + n 1 ) ( d G 2 ( v ) + n 1 ) ) = 2 λ ( M ¯ 2 ( G 2 ) + n 1 M ¯ 1 ( G 2 ) + n 1 2 m ¯ 2 ) + M 2 ( G 2 ) + n 1 M 1 ( G 2 ) + n 1 2 m 2 .

Therefore,

H λ * ( G 1 + G 2 ) = S 1 * + S 2 * + S 3 * = 2 λ ( n 2 M ¯ 1 ( G 1 ) + n 1 M ¯ 1 ( G 2 ) + M ¯ 2 ( G 1 ) + M ¯ 2 ( G 2 ) ) + 2 λ ( n 2 2 m ¯ 1 + n 1 2 m ¯ 2 ) + n 2 M 1 ( G 1 ) + n 1 M 1 ( G 2 ) + M 2 ( G 1 ) + M 2 ( G 2 ) + 4 m 1 m 2 + n 1 n 2 ( 2 m 1 + n 1 n 2 + 2 m 2 ) + n 2 2 m 1 + n 1 2 m 2 .

In the above theorem, if λ = 1 , then we can obtain D D * ( G 1 + G 2 ) . Replace separately G 1 and G 2 by K 1 and G in Theorem 2.1, we can obtain the following result.

Corollary 2.2. Let G be a connected graph with n vertices and m edges. Then

H λ * ( K 1 + G ) = 2 λ ( M ¯ 1 ( G ) + M ¯ 2 ( G ) + m ¯ ) + ( M 1 ( G ) + M 2 ( G ) ) + n 2 + 2 n m + m .

We can observe that M 1 ( C n ) = 4 n for n 3 , M 1 ( P n ) = 4 n 6 for n > 1 , and M ¯ 1 ( C n ) = 2 n ( n 3 ) , M ¯ 1 ( P n ) = 2 ( n 2 ) 2 . Hence, we can compute the formulae for modified generalized degree distance of fan graph K 1 + P n and wheel graph K 1 + C n (see Figure 1) in the following.

Example 2.1. H λ * ( K 1 + P n ) = 2 λ 1 ( 9 n 2 39 n + 44 ) + ( 3 n 2 + 7 n 15 ) .

H λ * ( K 1 + C n ) = 2 λ 1 9 n ( n 3 ) + 3 n ( n + 3 ) .

Next, we compute the exact formula for the modified generalized degree distance of the composition of two graphs. Before starting the discussion, we

first denote by A ( G ) the sum i , j = 1 i j n d G λ ( u i , u j ) d G ( u i ) . It is easy to deduce that

i , j = 1 i j n d G λ ( u i , u j ) d G ( u i ) = i , j = 1 i j n d G λ ( u i , u j ) d G ( u j ) .

By calculations we obtain the expressions for A ( P n ) and A ( C n ) as following:

A ( P n ) = i = 1 n 1 2 ( 2 n 2 i 1 ) i λ ,

Figure 1. The graphs P n + K 1 and C n + K 1 .

A ( C n ) = { i = 1 n 1 2 4 n i λ , n isodd , 2 1 λ n 1 + λ + i = 1 n 2 2 4 n i λ , n iseven .

we can also obtain the expressions for H λ * ( P n ) and H λ * ( C n ) :

H λ * ( P n ) = 2 ( n 1 ) λ + i = 2 n 1 8 ( i 1 ) ( n i ) λ .

H λ * ( C n ) = { i = 1 n 1 2 8 n i λ , n isodd , 4 n ( n 2 ) λ + i = 1 n 2 2 8 n i λ , n iseven .

These formulae are similar to the known results in [22] :

W λ ( P n ) = n i = 1 n 1 i λ i = 1 n 1 i λ + 1 ,

W λ ( C n ) = { n i = 1 n 1 2 i λ , n isodd , ( n 2 ) λ + 1 + n i = 1 n 2 2 i λ , n iseven .

Theorem 2.3. Let G 1 and G 2 be two graphs. Then

H λ * ( G 1 [ G 2 ] ) = 2 λ ( n 2 2 m ¯ 2 M 1 ( G 1 ) + n 1 M ¯ 2 ( G 2 ) + 2 n 2 m 1 M ¯ 1 ( G 2 ) ) + 2 n 2 ( m 2 M 1 ( G 1 ) + m 1 M 1 ( G 2 ) ) + n 1 M 2 ( G 2 ) + 4 n 2 2 m 2 A ( G 1 ) + 4 m 2 2 W λ ( G 1 ) + n 2 4 H λ * ( G 1 ) .

Proof. Set V ( G 1 ) = { u 1 , u 2 , , u n 1 } and V ( G 2 ) = { v 1 , v 2 , , v n 2 } . By 4), 8) of Lemma 2.1 and definition of H λ * ( G ) , we have

H λ * ( G 1 [ G 2 ] ) = { u , v } V ( G 1 [ G 2 ] ) d G 1 [ G 2 ] λ ( u , v ) ( d G 1 [ G 2 ] ( u ) d G 1 [ G 2 ] ( v ) ) = 1 2 ( u i , v k ) ( u j , v l ) d G 1 [ G 2 ] λ ( ( u i , v k ) , ( u j , v l ) ) ( n 2 d G 1 ( u i ) + d G 2 ( v k ) ) ( n 2 d G 1 ( u j ) + d G 2 ( v l ) ) = p = 1 n 1 k , l = 1 v k v l E ( G 2 ) n 2 d G 1 [ G 2 ] λ ( ( u p , v k ) , ( u p , v l ) ) ( n 2 2 d G 1 2 ( u p ) + n 2 d G 1 ( u p ) ( d G 2 ( v k ) + d G 2 ( v l ) ) + d G 2 ( v k ) d G 2 ( v l ) )

+ k , l = 1 n 2 i , j = 1 i j n 1 d G 1 [ G 2 ] λ ( ( u i , v k ) , ( u j , v l ) ) ( n 2 2 d G 1 ( u i ) d G 1 ( u j ) + n 2 d G 1 ( u i ) d G 2 ( v l ) + n 2 d G 1 ( u j ) d G 2 ( v k ) + d G 2 ( v k ) d G 2 ( v l ) ) + p = 1 n 1 k , l = 1 v k v l E ( G 2 ) n 2 d G 1 [ G 2 ] λ ( ( u i , v k ) , ( u j , v l ) ) ( n 2 2 d G 1 2 ( u p ) + n 2 d G 1 ( u p ) ( d G 2 ( v k ) + d G 2 ( v l ) ) + d G 2 ( v k ) d G 2 ( v l ) )

= 2 λ ( n 2 2 m ¯ 2 M 1 ( G 1 ) + n 1 M ¯ 2 ( G 2 ) + 2 n 2 m 1 M ¯ 1 ( G 2 ) ) + 2 n 2 ( m 2 M 1 ( G 1 ) + m 1 M 1 ( G 2 ) ) + n 1 M 2 ( G 2 ) + 4 n 2 2 m 2 A ( G 1 ) + 4 m 2 2 W λ ( G 1 ) + n 2 4 H λ * (G1)

In Theorem 2.3, H λ * ( G 1 [ G 2 ] ) = D D * ( G 1 [ G 2 ] ) if λ = 1 , and in the above proof, when u i = u j & v k v l E ( G 2 ) , d G 1 [ G 2 ] ( ( u i , v k ) , ( u j , v l ) ) = 1 ; when u i u j , d G 1 [ G 2 ] ( ( u i , v k ) , ( u j , v l ) ) = d G 1 ( u i , u j ) ; when u i = u j & v k v l E ( G 2 ) , d G 1 [ G 2 ] ( ( u i , v k ) , ( u j , v l ) ) = 2 by Lemma 2.1 4).

By composing paths or cycles with various small graphs, we can obtain classes of polymer-like graphs. As an application, we give the formulae of H λ * ( P n [ K 2 ] ) and H λ * ( C n [ K 2 ] ) , where P n [ K 2 ] and C n [ K 2 ] are open fence graph and closed fence graph (see Figure 2), respectively.

Example 2.2. H λ * ( P n [ K 2 ] ) = 25 n 32 + 2 4 ( H λ * ( P n ) + A ( P n ) ) + 4 W λ ( P n ) ,

H λ * ( C n [ K 2 ] ) = 25 n 8 + 2 4 ( H λ * ( C n ) + A ( C n ) ) + 4 W λ ( C n ) .

The following theorem characterizes the modified generalized degree distance of the disjunction of two graphs.

Theorem 2.4. Let G 1 and G 2 be two graphs. Then

H λ * ( G 1 G 2 ) = 2 λ ( n 2 ( n 2 2 + 2 n 2 m ¯ 2 4 m 2 ) M ¯ 2 ( G 1 ) + n 1 ( n 1 2 + 2 n 1 m ¯ 1 4 m 1 ) M ¯ 2 ( G 2 ) + n 2 2 m ¯ 2 M 1 ( G 1 ) + n 1 2 m ¯ 1 M 1 ( G 2 ) + 2 n 1 n 2 ( m 2 M ¯ 1 ( G 1 ) + m 1 M ¯ 1 ( G 2 ) ) ) + 2 λ ( ( M 1 ( G 2 ) n 2 M ¯ 1 ( G 2 ) ) M ¯ 2 ( G 1 ) + ( M 1 ( G 1 ) n 1 M ¯ 1 ( G 1 ) ) M ¯ 2 ( G 2 ) + ( n 1 n 2 M ¯ 1 ( G 1 ) M ¯ 1 ( G 2 ) n 1 M ¯ 1 ( G 1 ) M 1 ( G 2 ) n 2 M ¯ 1 ( G 2 ) M 1 ( G 1 ) )

+ M ¯ 2 ( G 1 ) M ¯ 2 ( G 2 ) ) + 4 n 2 2 m 1 2 m 2 + 4 n 1 2 m 2 2 m 1 + 2 n 1 m 2 ( n 2 2 2 m 2 ) M 1 ( G 1 ) + 2 n 2 m 1 ( n 1 2 2 m 1 ) M 1 ( G 2 ) + ( n 2 2 m 2 ) ( n 2 2 4 m 2 ) M 2 ( G 1 ) + ( n 1 2 m 1 ) ( n 1 2 4 m 1 ) M 2 ( G 2 ) n 1 n 2 M 1 ( G 1 ) M 1 ( G 2 ) + n 1 M 1 ( G 1 ) M 2 ( G 2 ) + n 2 M 1 ( G 2 ) M 2 ( G 1 ) M 2 ( G 1 ) M 2 ( G 2 ) .

Proof. By the definition of G 1 G 2 , we first present the following four sums:

Figure 2. The graphs P n [ K 2 ] and C n [ K 2 ] .

S 1 * = { x , y } V ( G 1 ) u v E ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = { x , y } V ( G 1 ) u v E ( G 2 ) n 2 2 d G 1 ( x ) d G 1 ( y ) + { x , y } V ( G 1 ) u v E ( G 2 ) n 1 2 d G 2 ( u ) d G 2 ( v ) + { x , y } V ( G 1 ) u v E ( G 2 ) n 1 n 2 ( d G 1 ( x ) d G 2 ( v ) + d G 1 ( y ) d G 2 (u))

{ x , y } V ( G 1 ) u v E ( G 2 ) n 2 d G 1 ( x ) d G 1 ( y ) ( d G 2 ( u ) + d G 2 ( v ) ) { x , y } V ( G 1 ) u v E ( G 2 ) n 1 d G 2 ( u ) d G 2 ( v ) ( d G 1 ( x ) + d G 1 ( y ) ) + { x , y } V ( G 1 ) u v E ( G 2 ) d G 1 ( x ) d G 1 ( y ) d G 2 ( u ) d G 2 ( v ) = 4 n 2 2 m 1 2 m 2 + 2 n 2 m 1 ( n 1 2 2 m 1 ) M 1 ( G 2 ) + ( n 1 2 2 m 1 ) 2 M 2 (G2)

S 2 * = x y E ( G 1 ) { u , v } V ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = x y E ( G 1 ) { u , v } V ( G 2 ) n 2 2 d G 1 ( x ) d G 1 ( y ) + x y E ( G 1 ) { u , v } V ( G 2 ) n 1 2 d G 2 ( u ) d G 2 ( v ) + x y E ( G 1 ) { u , v } V ( G 2 ) n 1 n 2 ( d G 1 ( x ) d G 2 ( v ) + d G 1 ( y ) d G 2 (u))

x y E ( G 1 ) { u , v } V ( G 2 ) n 2 d G 1 ( x ) d G 1 ( y ) ( d G 2 ( u ) + d G 2 ( v ) ) x y E ( G 1 ) { u , v } V ( G 2 ) n 1 d G 2 ( u ) d G 2 ( v ) ( d G 1 ( x ) + d G 1 ( y ) ) + x y E ( G 1 ) { u , v } V ( G 2 ) d G 1 ( x ) d G 1 ( y ) d G 2 ( u ) d G 2 ( v ) = 4 n 1 2 m 2 2 m 1 + 2 n 1 m 2 ( n 2 2 2 m 2 ) M 1 ( G 1 ) + ( n 2 2 2 m 2 ) 2 M 2 (G1)

S 3 * = x y E ( G 1 ) u v E ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = x y E ( G 1 ) u v E ( G 2 ) n 2 2 d G 1 ( x ) d G 1 ( y ) + x y E ( G 1 ) u v E ( G 2 ) n 1 2 d G 2 ( u ) d G 2 ( v ) + x y E ( G 1 ) u v E ( G 2 ) n 1 n 2 ( d G 1 ( x ) d G 2 ( v ) + d G 1 ( y ) d G 2 (u))

x y E ( G 1 ) u v E ( G 2 ) n 2 d G 1 ( x ) d G 1 ( y ) ( d G 2 ( u ) + d G 2 ( v ) ) x y E ( G 1 ) u v E ( G 2 ) n 1 d G 2 ( u ) d G 2 ( v ) ( d G 1 ( x ) + d G 1 ( y ) ) + x y E ( G 1 ) u v E ( G 2 ) d G 1 ( x ) d G 1 ( y ) d G 2 ( u ) d G 2 ( v ) = n 2 2 m 2 M 2 ( G 1 ) + n 1 n 2 M 1 ( G 1 ) M 1 ( G 2 ) n 2 M 1 ( G 2 ) M 2 ( G 1 ) + n 1 2 m 1 M 2 ( G 2 ) n 1 M 1 ( G 1 ) M 2 ( G 2 ) + M 2 ( G 1 ) M 2 (G2)

S 4 * = x y E ( G 1 ) x y u v E ( G 2 ) u v 2 λ ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) + x y E ( G 1 ) u V ( G 2 ) 2 λ ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 (u))

( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) + x V ( G 1 ) u v E ( G 2 ) 2 λ ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 (v))

= 2 λ ( ( n 2 3 + 2 n 2 2 m ¯ 2 4 n 2 m 2 ) M ¯ 2 ( G 1 ) + ( n 1 3 + 2 n 1 2 m ¯ 1 4 n 1 m 1 ) M ¯ 2 ( G 2 ) + 2 n 1 n 2 ( m 2 M ¯ 1 ( G 1 ) + m 1 M ¯ 1 ( G 2 ) ) + n 1 2 m ¯ 1 M 1 ( G 2 ) + n 2 2 m ¯ 2 M 1 ( G 1 ) ) + 2 λ ( ( n 1 n 2 M ¯ 1 ( G 1 ) M ¯ 1 ( G 2 ) n 1 M 1 ( G 2 ) M ¯ 1 ( G 1 ) n 2 M 1 ( G 1 ) M ¯ 1 ( G 2 ) ) + ( M 1 ( G 2 ) n 2 M ¯ 1 ( G 2 ) ) M ¯ 2 ( G 1 ) + ( M 1 ( G 1 ) n 1 M ¯ 1 ( G 1 ) ) M ¯ 2 ( G 2 ) ) + 2 λ M ¯ 2 ( G 1 ) M ¯ 2 ( G 2 ) .

Thus, we can obtain the result of Theorem 2.4 by the formula H λ * ( G 1 G 2 ) = S 1 * + S 2 * + S 4 * S 3 * .

Finally, we consider the modified generalized degree distance of the symmetric difference of two graphs.

Theorem 2.5. Let G 1 and G 2 be two graphs. Then

H λ * ( G 1 G 2 ) = 2 λ ( n 2 ( n 2 2 + 2 n 2 m ¯ 2 8 m 2 ) M ¯ 2 ( G 1 ) + n 1 ( n 1 2 + 2 n 1 m ¯ 1 8 m 1 ) M ¯ 2 ( G 2 ) + n 2 2 m ¯ 2 M 1 ( G 1 ) + n 1 2 m ¯ 1 M 1 ( G 2 ) + 2 n 1 n 2 ( m 2 M ¯ 1 ( G 1 ) + m 1 M ¯ 1 ( G 2 ) ) ) + 2 λ ( 2 ( 2 M 1 ( G 2 ) n 2 M ¯ 1 ( G 2 ) ) M ¯ 2 ( G 1 ) + 2 ( 2 M 1 ( G 1 ) n 1 M ¯ 1 ( G 1 ) ) M ¯ 2 ( G 2 ) + n 1 n 2 M ¯ 1 ( G 1 ) M ¯ 2 ( G 2 ) 2 n 1 M ¯ 1 ( G 1 ) M 1 ( G 2 ) 2 n 2 M ¯ 1 ( G 2 ) M 1 (G1)

+ 2 2 M ¯ 2 ( G 1 ) M ¯ 2 ( G 2 ) ) + 4 n 2 2 m 1 2 m 2 + 4 n 1 2 m 2 2 m 1 + 2 n 1 m 2 ( n 2 2 4 m 2 ) M 1 ( G 1 ) + 2 n 2 m 1 ( n 1 2 4 m 1 ) M 1 ( G 2 ) + ( n 2 2 2 m 2 ) ( n 2 2 8 m 2 ) M 2 ( G 1 ) + ( n 1 2 2 m 1 ) ( n 1 2 8 m 1 ) M 2 ( G 2 ) 2 n 1 n 2 M 1 ( G 1 ) M 1 ( G 2 ) + 4 n 1 M 1 ( G 1 ) M 2 ( G 2 ) + 4 n 2 M 1 ( G 2 ) M 2 ( G 1 ) 8 M 2 ( G 1 ) M 2 ( G 2 ) .

Proof. Similar to the proof of Theorem 2.4, we consider four sums:

S 1 * = { x , y } V ( G 1 ) u v E ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = 4 n 2 2 m 1 2 m 2 + 2 n 2 m 1 ( n 1 2 4 m 1 ) M 1 ( G 2 ) + ( n 1 2 4 m 1 ) 2 M 2 ( G 2 ) .

S 2 * = x y E ( G 1 ) { u , v } V ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = 4 n 1 2 m 2 2 m 1 + 2 n 1 m 2 ( n 2 2 4 m 2 ) M 1 ( G 1 ) + ( n 2 2 4 m 2 ) 2 M 2 ( G 1 ) .

S 3 * = x y E ( G 1 ) u v E ( G 2 ) ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = n 2 2 m 2 M 2 ( G 1 ) + n 1 n 2 M 1 ( G 1 ) M 1 ( G 2 ) 2 n 2 M 1 ( G 2 ) M 2 ( G 1 ) + n 1 2 m 1 M 2 ( G 2 ) 2 n 1 M 1 ( G 1 ) M 2 ( G 2 ) + 4 M 2 ( G 1 ) M 2 ( G 2 ) .

S 4 * = x y E ( G 1 ) x y u v E ( G 2 ) u v 2 λ ( n 2 d G 1 ( x ) + n 1 d G 2 ( u ) d G 1 ( x ) d G 2 ( u ) ) ( n 2 d G 1 ( y ) + n 1 d G 2 ( v ) d G 1 ( y ) d G 2 ( v ) ) = 2 λ ( ( n 2 3 + 2 n 2 2 m ¯ 2 8 n 2 m 2 ) M ¯ 2 ( G 1 ) + ( n 1 3 + 2 n 1 2 m ¯ 1 8 n 1 m 1 ) M ¯ 2 ( G 2 ) + 2 n 1 n 2 ( m 2 M ¯ 1 ( G 1 ) + m 1 M ¯ 1 ( G 2 ) ) + n 1 2 m ¯ 1 M 1 ( G 2 ) + n 2 2 m ¯ 2 M 1 ( G 1 ) )

+ 2 λ ( ( n 1 n 2 M ¯ 1 ( G 1 ) M ¯ 1 ( G 2 ) 2 n 1 M 1 ( G 2 ) M ¯ 1 ( G 1 ) 2 n 2 M 1 ( G 1 ) M ¯ 1 ( G 2 ) ) + 2 ( 2 M 1 ( G 2 ) n 2 M ¯ 1 ( G 2 ) ) M ¯ 2 ( G 1 ) + 2 ( 2 M 1 ( G 1 ) n 1 M ¯ 1 ( G 1 ) ) M ¯ 2 ( G 2 ) ) + 2 λ + 2 M ¯ 2 ( G 1 ) M ¯ 2 ( G 2 ) .

Therefore, we can obtain the result of Theorem 2.5 by H λ * ( G 1 G 2 ) = S 1 * + S 2 * + S 4 * 2 S 3 * .

Remark. In Section 2, we present the explicit formulae of the modified generalized degree distance for four types of graph operations containing G 1 + G 2 , G 1 [ G 2 ] , G 1 G 2 and G 1 G 2 , and we give some examples. It implies that our results are convenient to compute the modified generalized degree distance of these graph operations. Moreover, if λ = 1 , then H λ * ( G ) = D D * ( G ) . This implies that our results are related to the product-degree distance. In [16] Hamzeh et al. construct graph polynomial as following:

H λ * ( G , x ) = { u , v } V ( G ) ( d G ( u ) d G ( v ) ) x d λ ( u , v ) .

It is easy to see that the results of our Theorems 2.1, 2.3, 2.4 and 2.5 are exactly the first derivatives at point x = 1 of the graph polynomial H λ * ( G , x ) . Thus we obtain the relation between the modified generalized degree distance polynomial and Wiener-type invariant polynomial for graphs.

Funding

This work is supported by the National Natural Science Foundation of China (11761056) and by Natural Science Foundation of Qinghai Province (2018-ZJ-717), and by the Fund of Qinghai Nationalities University (2016XJG08).

Cite this paper

Lv, S.M. (2018) Modified Generalized Degree Distance of Some Graph Operations. Advances in Pure Mathematics, 8, 548-558. https://doi.org/10.4236/apm.2018.86032

References

  1. 1. Bondy, J. and Murty, U. (1976) Graph Theory with Applications. Elsevier, New York. https://doi.org/10.1007/978-1-349-03521-2

  2. 2. Gutman, I. and Polansky, O. (1986) Mathematical Concepts in Organic Chemistry. Springer-Verlag, Berlin. https://doi.org/10.1007/978-3-642-70982-1

  3. 3. Wiener, H. (1947) Structural Determination of Paraffin Boiling Point. Journal of the American Chemical Society, 69, 17-20. https://doi.org/10.1021/ja01193a005

  4. 4. Dobrynin, A. and Kochetova, A. (1994) Degree Distance of a Graph: A Degree Analogue of the Wiener Index. Journal of Chemical Information and Computer Sciences, 34, 1082-1086. https://doi.org/10.1021/ci00021a008

  5. 5. Gutman, I. (1994) Selected Properties of the Schultz Molecular Topogical Index. Journal of Chemical Information and Computer Sciences, 34, 1087-1089. https://doi.org/10.1021/ci00021a009

  6. 6. Gutman, I. and Klavzarc, S. (1997) Wiener Number of Vertex-Weighted Graphs and a Chemical Applications. Discrete Applied Mathematics, 80, 73-81. https://doi.org/10.1016/S0166-218X(97)00070-X

  7. 7. Gutman, I. (1997) A Property of the Wiener Number and Its Modifications. Indian Journal of Chemistry: Section A, 36, 128-132.

  8. 8. Gutman, I., Rada, J. and Araujo, O. (2000) The Wiener Index of Starlike Trees and a Related Partial Order. MATCH Communications in Mathematical and in Computer Chemistry, 42, 145-154.

  9. 9. Hua, H. (2009) Wiener and Schultz Molecular Topological Indices of Graphs with Specified Cut Edges. MATCH Communications in Mathematical and in Computer Chemistry, 16, 643-651.

  10. 10. Dankelmann, P., Gutman, I., Mukwembi, S. and Swart, H.C. (2009) On the Degree Distance of a Graph. Discrete Applied Mathematics, 157, 2773-2777. https://doi.org/10.1016/j.dam.2009.04.006

  11. 11. Feng, L., Liu, W., Ili, A. and Yu, G. (2013) Degree Distance of Unicyclic Graphs with Given Matching Number. Graphs and Combinatorics, 5, 449-462. https://doi.org/10.1007/s00373-012-1143-5

  12. 12. Ilic, A., Stevanovic, D., Feng, L., Yu, G. and Dankelmann, P. (2011) Degree Distance of Unicyclic and bicyclic Graphs. Discrete Applied Mathematics, 159, 779-788. https://doi.org/10.1016/j.dam.2011.01.013

  13. 13. Tomescu, I. (2008) Properties of Connected Graphs Having Minimum Degree Distance. Discrete Math, 309, 2745-2748. https://doi.org/10.1016/j.disc.2008.06.031

  14. 14. Tomescu, I. (2010) Ordering Connected Graphs Having Small Degree Distances. Discrete Applied Mathematics, 158, 1714-1717. https://doi.org/10.1016/j.dam.2010.05.023

  15. 15. Sagan, B., Yeh, Y. and Zhang, P. (1996) The Wiener Polynomial of a Graph. International Journal of Quantum Chemistry, 60, 959-969. 3.0.CO;2-W>https://doi.org/10.1002/(SICI)1097-461X(1996)60:5<959::AID-QUA2>3.0.CO;2-W

  16. 16. Hamzeh, A., Iranmanesh, A. and Hossein-Zadeh, S. (2013) Some Results on Generalized Degree Distance. Open Journal of Discrete Mathematics, 3, 143-150. https://doi.org/10.4236/ojdm.2013.33026

  17. 17. Hamzeh, A., Iranmanesh, A., Hossein-Zadeh, S. and Diudea, M. (2012) Generalized Degree Distance of Trees, Unicyclic and Bicyclic Graphs. Studia Universitatis Babes-Bolyai. Chemia, 4, 73-85.

  18. 18. Imrich, W. and Klavzarc, S. (2000) Product Graphs: Structure and Recognition. John Wiley & Sons, New York.

  19. 19. Gutman, I. and Trinajstic, N. (1972) Graph Theory and Molecular Orbitals. Total φ-Electron Energy of Alternant Hydrocarbons. Chemical Physics Letters, 17, 535-538. https://doi.org/10.1016/0009-2614(72)85099-1

  20. 20. Doslic, T. (2008) Vertex-Weighted Wiener Polynomials for Composite Graphs. Ars Mathematica Contemporanea, 1, 66-80.

  21. 21. Khalifeh, M., Yousefi-Azari, H. and Ashrafi, A. (2008) The Hyper-Wiener Index of Graph Operations. Computers & Mathematics with Applications, 56, 1402-1407. https://doi.org/10.1016/j.camwa.2008.03.003

  22. 22. Hossein-Zadeh, S., Hamzeh, A. and Ashrafi, A. (2009) Wiener-Type Invariants of Some Graph Operations. Filomat, 29, 103-113. https://doi.org/10.2298/FIL0903103H