The Wiener Index of an Undirected Power Graph

Abstract

The undirected power graph P(Zn) of a finite group Zn is the graph with vertex set G and two distinct vertices u and v are adjacent if and only if uv and or . The Wiener index W(P(Zn)) of an undirected power graph P(Zn) is defined to be sum of distances between all unordered pair of vertices in P(Zn). Similarly, the edge-Wiener index We(P(Zn)) of P(Zn) is defined to be the sum of distances between all unordered pairs of edges in P(Zn). In this paper, we concentrate on the wiener index of a power graph , P(Zpq) and P(Zp). Firstly, we obtain new results on the wiener index and edge-wiener index of power graph P(Zn), using m,n and Euler function. Also, we obtain an equivalence between the edge-wiener index and wiener index of a power graph of Zn.

Share and Cite:

Aşkin, V. and Büyükköse, Ş. (2021) The Wiener Index of an Undirected Power Graph. Advances in Linear Algebra & Matrix Theory, 11, 21-29. doi: 10.4236/alamt.2021.111003.

1. Introduction

We define an undirected power graph P ( G ) for a group G as follows. Let us denote the cylic subgroup genarated by u G by u , that is, u = { u m | m } , where denotes the set of naturel numbers. The graph P ( G ) is an undirected graph where vertex set is G and two vertices u , v G are adjacent if and only if u v and u v or v v (which is equivalent to say u v and u m = v or v m = u for some positive integer m.) [1] [2] [3] [4].

For a graph G, let deg ( u ) and d ( u , v ) denote the degree of a vertex u V ( G ) and the distance between vertices u , v V ( G ) , respectively. Let L ( G ) denote the line graph of G, that is, the graph with vertex set E ( G ) and two distinct edges e , f E ( G ) adjacent in L ( G ) whenever they share an end-vertex in G. Furthermore, for, f E ( G ) , we let d ( e , f ) denote the distance between e and f in the line graph L ( G ) .

We consider the power graph P ( Z n ) for the additive group Z n of integers modulo n. The diameter of a graph G is the greatest distance between any pair of vertices, and denoted by d i a m ( G ) . In P ( Z n ) , the distance is one if the vertices is adjacent and the distance is two if the vertices is non adjacent. Therefore, d i a m ( P ( Z n ) ) = 2 . The order an element g ¯ in Z n is denoted by ( g ¯ ) or | g | . For a positive integer n, ϕ ( n ) denotes the Euler’s totient function of n.

In this paper, the wiener index and the edge-wiener index, denoted by W ( G ) and W e ( G ) , respectively and they are defined as follows:

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

W e ( G ) = 1 2 { e , f } E ( G ) d ( e , f )

Now, we give some theorem and corollary in literature. Using our main theorems;

Theorem 1. ( [5] ) For each finite group, the number of edges of the undirected power graph P ( G ) is given by the formula

E ( P ( G ) ) = 1 2 g G { 2 o ( g ) ϕ ( o ( g ) ) 1 }

Corollary 2. ( [6] ) The number of edges of the undirected power graph P ( Z n ) is given by 1 2 d | n { 2 d ϕ ( d ) 1 } ϕ ( d ) .

Theorem 3. ( [3] ) Let G be connected graph with n vertices and m edges. If d i a m ( G ) 2 , Then W ( G ) = n ( n 1 ) m .

Theorem 4. ( [5] ) A finite group has a complete undirected power graph if and only if it is cyclic and has order equal to pk, where p is a prime and k is a nonnegative integer.

2. Main Results

In this section, our aim is to give our main results on the Wiener index and the edge-Wiener index of an undirected power graph P ( Z n ) for n = p k , or n = p q , where p and q are distinct prime numbers and k is a nonnegative integer.

Theorem 5. Let P ( Z n ) be an undirected power graph of with n vertices and m edges. Then

W ( P ( Z n ) ) = 1 2 { u , v } V ( P ( Z n ) ) { 1 , u v 2 , u v

Proof. Let

R = { { u , v } V ( P ( Z n ) ) | u ~ v if only if u v , u v or v u } be a set. In P ( Z n ) , for { u , v } V ( P ( Z n ) ) , there are two cases; If u v then d ( u , v ) = 2 . Otherwise, i.e. u v , then d ( u , v ) = 1 . Therefore

W ( P ( Z n ) ) = 1 2 { u , v } V ( P ( Z n ) ) d ( u , v ) = 1 2 ( { u , v } R d ( u , v ) + { u , v } R d ( u , v ) ) = 1 2 { u , v } R 1 + 1 2 { u , v } R 2 = 1 2 { u , v } V ( P ( Z n ) ) { 1 , { u , v } R 2 , { u , v } R

For definition of R, we obtain. Thus

W ( G ) = 1 2 { u , v } V ( P ( Z n ) ) { 1 , u v 2 , u v

the proof is complete.

Corollary 6. Let p and k is prime number and nonnegative integer, respectively. For P ( Z p k ) power graph of order p k and m edges,

W ( P ( Z p k ) ) = ( p k 2 ) .

Proof. In [2], If n = p k then P ( Z n ) = K n . For any u V ( Z p k ) , d ( u ) = p k 1 .

R c = { { u , v } V ( P ( Z n ) ) | u v } =

Thus

W ( P ( Z p k ) ) = 1 2 { u , v } V ( P ( Z n ) ) { 1 , u v 2 , u v = 1 2 ( { u , v } R d ( u , v ) + { u , v } d ( u , v ) ) = 1 2 ( { u , v } R 1 + { u , v } d ( u , v ) ) = 1 2 { u , v } R 1 = 1 2 p k ( p k 1 ) = ( p k 2 )

Therefore the proof is proved.

Theorem 7. Let P ( Z n ) be a power graph of with n vertices and m edges. Then

W ( P ( Z n ) ) = 1 2 { ( 2 n 2 ) + g = 0 n 1 ( ϕ ( | g ¯ | ) 2 | g ¯ | ) }

Proof. If we consider Theorem 3. for = P ( Z n ) , we write

W ( P ( Z n ) ) = n ( n 1 ) m

m = 1 2 g Z n { 2 o ( g ) ϕ ( o ( g ) ) 1 } .

If we put the value of m into the formula, we obtain

W ( P ( Z n ) ) = n ( n 1 ) m = n ( n 1 ) 1 2 g Z n { 2 o ( g ) ϕ ( o ( g ) ) 1 } = n 2 n + 1 2 g Z n { ϕ ( o ( g ) ) 2 o ( g ) } 1 2 g Z n 1 = n 2 n + n 2 + 1 2 g Z n { ϕ ( o ( g ) ) 2 o ( g ) } = { n 2 n 2 + 1 2 g = 0 n 1 ( ϕ ( | g ¯ | ) 2 | g ¯ | ) }

W ( P ( Z n ) ) = 1 2 { ( 2 n 2 ) + g = 0 n 1 ( ϕ ( | g ¯ | ) 2 | g ¯ | ) }

Thus, the proof is complete.

Corollary 8. Let P ( Z n ) be a power graph of with n = p , where p is a prime number. Then

W ( P ( Z n ) ) = ( P 2 ) .

Proof. Let n = p be a prime number. Then

W ( P ( Z p ) ) = 1 2 { ( 2 p 2 ) + g = 0 p 1 ( ϕ ( | g ¯ | ) 2 | g ¯ | ) } = 1 2 [ 2 p ( 2 p 1 ) 2 + ϕ ( | 0 ¯ | ) + ϕ ( | 1 ¯ | ) + + ϕ ( | p 1 ¯ | ) 2 ( | 0 ¯ | + | 1 ¯ | + + | p 1 ¯ | ) ] = 1 2 [ 2 p 2 p 1 + ( ϕ ( | 1 ¯ | ) + + ϕ ( | p 1 ¯ | ) ) 2 ( | 1 ¯ | + + | p 1 ¯ | ) ] = 1 2 [ 2 p 2 p 1 + ( p 1 ) ϕ ( p ) 2 ( p 1 ) p ] = 1 2 [ 2 p 2 p 1 + ( p 1 ) 2 2 p 2 + 2 p ] = ( p 2 )

Theorem 9. Let P ( Z n ) be a power graph of with n vertices and m edges. Then

W ( P ( Z n ) ) = 1 2 { ( 2 n 2 ) + d | n ϕ ( d ) ( ϕ ( d ) 2 d ) } .

Proof. Where P ( Z n ) is power graph = P ( Z n ) , using theorem 3. And corollary 2, we obtain

W ( P ( Z n ) ) = n ( n 1 ) m

m = 1 2 d | n { 2 d ϕ ( d ) 1 } ϕ ( d )

If we write this m in formula for W ( P ( Z n ) )

W ( P ( Z n ) ) = n ( n 1 ) m = n ( n 1 ) 1 2 d | n { 2 d ϕ ( d ) 1 } ϕ ( d ) = n 2 n + 1 2 d | n ϕ ( d ) 2 + 1 2 d | n ϕ ( d ) d | n d ϕ ( d ) = n 2 n 2 + 1 2 d | n ϕ ( d ) ( ϕ ( d ) 2 d )

W ( P ( Z n ) ) = 1 2 { ( 2 n 2 ) + d | n ϕ ( d ) ( ϕ ( d ) 2 d ) } .

End of proof.

Corollary 10. Let P ( Z n ) be a power graph of with n = p q vertices and m edges, wherep and q are distinct prime numbers. Then

W ( P ( Z p q ) ) = m + 2 ϕ ( p q )

or equiently

W ( P ( Z p q ) ) = ( p q 2 ) + ϕ ( p q ) .

Proof. If we write n = p q in theorem 9., we obtain

W ( P ( Z p q ) ) = 1 2 { ( 2 p q 2 ) + d | p q ϕ ( d ) ( ϕ ( d ) 2 d ) } = 1 2 [ p q ( 2 p q 1 ) + ϕ ( 1 ) ( ϕ ( 1 ) 2 1 ) + ϕ ( p ) ( ϕ ( p ) 2 p ) + ϕ ( q ) ( ϕ ( q ) 2 q ) + ϕ ( p q ) ( ϕ ( p q ) 2 p q ) ] = 1 2 [ p 2 q 2 + p q 2 p 2 q + 2 ] = [ p 2 q 2 p q 2 + p q p q + 1 ] = [ ( p q 2 ) ϕ ( p q ) ] + 2 ϕ ( p q ) (*)

On the other hand;

W ( P ( Z p q ) ) = p q ( p q 1 ) m = ( p q 2 ) + ϕ ( p q )

where

m = ( p q 2 ) ϕ ( p q ) (**)

(**) equation put in (*) equation, we obtain,

W ( P ( Z p q ) ) = m + 2 ϕ ( p q ) .

This completes the proof.

On the other hand using m in (**), we obtain

W ( P ( Z p q ) ) = m + 2 ϕ ( p q ) = ( p q 2 ) ϕ ( p q ) + 2 ϕ ( p q ) = ( p q 2 ) + ϕ ( p q )

This completes the proof.

Theorem 11. If P ( Z n ) is a power graph of order n = p k or n = p q and m edges, where p and q are distinct prime and k is a nonnegative integer. Then

m a k s { W ( P ( Z n ) ) } = ( n + 1 2 )

and

min { W ( P ( Z n ) ) } = ( n 2 )

Proof. If n = p k in Corollary 6.

W ( P ( Z p k ) ) = ( p k 2 ) .

And so

min { W ( P ( Z n ) ) } = ( n 2 )

And if n = p q in Corollary 10.

W ( P ( Z p q ) ) = ( p q 2 ) + ϕ ( p q )

therefore

W ( P ( Z n ) ) ( n 2 ) + ϕ ( n ) .

Also

ϕ ( n ) n .

We write

W ( P ( Z n ) ) ( n 2 ) + ϕ ( n ) ( n 2 ) + n .

And so,

m a k s { W ( P ( Z n ) ) } = ( n + 1 2 ) .

Theorem 12. If P ( Z n ) is a power graph of order n = p k and m edges, where p is prime and k is a nonnegative integer. Then

W e ( P ( Z n ) ) = 3 { ( n 3 ) + d i a m ( L ( P ( Z n ) ) ) ( n 4 ) } .

Proof. For P ( Z p k ) power graph, E ( P ( Z n ) ) = ( n 2 ) and u V ( P ( Z n ) ) , d ( u ) = n 1 .

Let’s consider to this figure in P ( Z p k ) power graph any e n ¯ , n 1 ¯ E ( P ( Z p k ) ) . For P ( Z p k ) power graph of Line graph as shown in Figure 1.

Choose the random e n ¯ , n 1 ¯ E ( P ( Z p k ) ) edge and this corner in neighborhood L ( P ( Z n ) ) line graph in Figure 2. In the same way, with e n ¯ , n 1 ¯ V ( L ( P ( Z p k ) ) ) point neighborhood amount of points 2 ( n 2 ) . In the same way e n ¯ , n 1 ¯ neighborhood with corner amount of point m 1 2 ( n 2 ) and therefore V ( L ( P ( Z p k ) ) ) if each elements for calculated and if edge-Wiener index identified we have the following result.

In edge-Wiener index

W e ( P ( Z p k ) ) = 1 2 { e , f } E ( P ( Z n ) ) d ( e , f ) = 1 2 { u v = e [ ( d ( u ) + d ( v ) 2 ) ] + u v = e [ d i a m ( L ( P ( Z n ) ) ) ( ( m 1 ) ( d ( u ) + d ( v ) 2 ) ) ] } = 1 2 { ( n 2 ) [ 2 ( n 2 ) + d i a m ( L ( P ( Z n ) ) ) ( ( n 2 ) 1 2 ( n 2 ) ) ] } = [ n ( n 1 ) ( n 2 ) 2 + n ( n 1 ) 4 d i a m ( L ( P ( Z n ) ) ) ( n 2 5 n 6 2 ) ] = 3 ( n 3 ) + n ( n 1 ) ( n 2 ) ( n 3 ) 8 d i a m ( L ( P ( Z n ) ) )

W e ( P ( Z p k ) ) = 3 [ ( n 3 ) + d i a m ( L ( P ( Z n ) ) ) ( n 4 ) ]

Concluded, namely the prove end.

Theorem 13. If P ( Z n ) is a power graph of order n = p k and m edges, where p is prime and k is a nonnegative integer. Then

Figure 1. Power grap of Z p k .

Figure 2. Line graph of P ( Z n ) .

W e ( P ( Z n ) ) = ( n 1 2 ) W ( P ( Z n ) )

Proof. n = p k ( Z + ) is in W ( P ( Z n ) ) = ( n 2 ) . In the same way,

Case 1. for n = 2 , 3 and according to d i a m ( L ( P ( Z n ) ) ) = 1 , W e ( P ( Z 2 ) ) = 0 , therefore W e ( P ( Z 3 ) ) = W ( P ( Z 3 ) ) ve ( 3 1 2 ) = 1 , namely this equation the proof.

Case 2. For n 2 , 3 is d i a m ( L ( P ( Z n ) ) ) = 2 in theorem 12.,

W e ( P ( Z n ) ) = 3 [ ( n 3 ) + d i a m ( L ( P ( Z n ) ) ) ( n 4 ) ] = 3 [ ( n 3 ) + 2 ( n 4 ) ] = 1 2 n ( n 1 ) [ ( n 2 ) + ( ( n 2 ) ( n 3 ) 2 ) ] = ( n 2 ) ( n 2 ) [ 1 + n 3 2 ] = ( n 1 2 ) W ( P ( Z n ) )

Thus the proof is completed.

3. Conclusion

We will show the undirected power graph of a Group G with P(G). Here, the undirected P(Zn) Power graph of the group (Zn, +) according to N = pk and n = pq, with p, q being different primes and k being positive integers, is considered and new theorems and results on the Wiener index calculations of these power graphs with the help of Euler function are have been obtained.

Acknowledgements

This paper is derived from the first author’s PH’s thesis.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1] Alhevaz, A., Baghipuri, M. and Shang, Y. (2019) On Generalized Distance Gaussian Estrada Index of Graphs. Symmetry, 11, 1276.
https://doi.org/10.3390/sym11101276
[2] Iran Manesh, A., Gutman, I., Khormali, O. and Mahmiani, A. (2009) The Edge Versions of the Wiener Index. MATCH Communications in Mathematical and in Computer Chemistry, 61, 663-672.
[3] Chattopadhyay, S. and Panigrahi, P. (2017) On Sum of Powers of the Laplacian Eigenvalues of Power Graphs of Certain Finite Groups. Electronic Notes in Discrete Mathematics, 63, 137-143.
[4] Walikar, H.B., Shigehalli, V.S. and Ramane, H.S. (2004) Bounds on the Wiener Index of a Graph. MATCH Communications in Mathematical and in Computer Chemistry, 50, 117-132.
[5] Wiener, H. (1947) Structural Determination of Paraffin Boiling Points, Journal of the American Chemical Society, 69, 17-20.
[6] Chakrabarty, I. Ghosh, S. and Sen, M.K. (2009) Undirected Power Graphs of Semigroups. Semigroup Forum, 78, 410-426.

Copyright © 2021 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.