Advanced
SOME NEW RESULTS ON IRREGULARITY OF GRAPHS†
SOME NEW RESULTS ON IRREGULARITY OF GRAPHS†
Journal of Applied Mathematics & Informatics. 2014. Sep, 32(5_6): 675-685
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : January 15, 2014
  • Accepted : April 04, 2014
  • Published : September 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
M. TAVAKOLI
F. RAHBARNIA
A. R. ASHRAFI

Abstract
Suppose G is a simple graph. The irregularity of G, irr ( G ), is the summation of imb ( e ) over all edges uv = e G , where imb ( e ) = | deg ( u ) ∈ deg ( v )|. In this paper, we investigate the behavior of this graph parameter under some old and new graph operations. AMS Mathematics Subject Classification : 05C12.
Keywords
1. Introduction
The degree−based graph invariants are parameters defined by degrees of vertices. The first of such graph parameters was introduced by Gutman and Trinajstić [10] . Suppose G is a graph e = uv E ( G ). The first Zagreb index of G is defined as M 1 ( G ) = Σ vV (G) deg ( v ) 2 . There are a lot of works on Zagreb group invariants and interested readers can be consulted [3 , 8 , 11 , 16 , 17] for more information on this topic. The imbalance of e is defined as imb ( e ) = | deg ( u )− deg ( v )|. The summation of imbalances over all edges of G is denoted by irr ( G ). Albertson [2] , named this parameter “irregularity” of the graph G . After this paper, there was a lot of research considering the irregularity index, see [12 , 14 , 15] for details. It is easy to see that M 1 ( G ) = Σ e=uvE (G) [ deg ( u ) + deg ( v )]. Fath-Tabar [9] , unaware from the seminal paper of Albertson and because of similarity between M 1 and irr used the term “third Zagreb index” for “irregularity”.
Albertson [2] computed the maximum irregularity of various classes of graphs. As a consequence, he proved that the irregularity of an arbitrary graph with n vertices is less than
PPT Slide
Lager Image
and this bound is tight. Some of the present authors [20] , characterized the graphs with minimum and maximum values of irregularity. Luo and Zhou [18] determined the maximum irregularity of trees and unicyclic graphs with a given number of vertices and matching number. They also characterized the extremal graphs with the mentioned property. Zhou and Luo [22] , established an upper bound for irr ( G ) in terms of n,m , and r , where n is the order of G , m ≥ 1 is its size, and G is assumed to have no complete subgraph of order r + 1 where 2 ≤ r n − 1. They also provided new upper bounds for the irregularity of trees and unicyclic graphs. These are both functions of the number of pendant vertices of the graph under consideration. For each of these three inequalities, the authors supplied a characterization of all graphs which attain the bound. Henning and Rautenbach [15] obtained the structure of bipartite graphs having maximum possible irregularity with given cardinalities of its bipartition and given number of edges. They derived a result for bipartite graphs with given cardinalities of its bipartition and presented an upper bound on the irregularity of these graphs. In particular, they shown that if G is a bipartite graph of order n with a bipartition of equal cardinalities, then
PPT Slide
Lager Image
while if G is a bipartite graph with partite sets of cardinalities n 1 and n 2 , where n 1 ≥ 2 n2 , then irr ( G ) ≤ irr ( K n1 , n2 ).
Abdo and Dimitrov [1] introduced the concept of total irregularity of a graph G and obtain some exact formula for computing total irregularity of some old graph operations. The aim of this paper is to compute formulas for the regularity of graphs under some old and new graph invariants.
Throughout this paper the path, complete and star graphs of order n are denoted by by Pn , Kn and Sn , respectively. The degree of a vertex v is denoted by degG ( v ). We denote by Δ( G ) the maximum degree of vertices of G .
Lemma 1.1. Let G be a connected graph on n, n > 2 vertices. If G has exactly k pendant vertices then irr ( G ) ≽ k, with equality if and only if
PPT Slide
Lager Image
Proof . Suppose u is a pendant vertex of G and v V ( G ) is a vertex adjacent to u . Since | V ( G )| > 2, deg ( v ) ≽ 2 and so | deg ( u )− deg ( v )| ≽ 1. But, G has exactly k pendant vertices, and so irr ( G ) ≽ k . Notice that irr ( G ) = k if and only if degG ( u ) = 1 or 2, for each vertex u V ( G ). This implies that
PPT Slide
Lager Image
Corollary 1.2. Let T be a tree with Δ( T ) > 1. Then irr ( T ) ≽ Δ( T ).
Proof . By assumption, T has at least Δ( T ) pendant vertices and so, by Lemma 1.1, irr ( T ) ≽ Δ( T ).
Lemma 1.3. Let T be a tree with n > 2 vertices. Then
PPT Slide
Lager Image
and the lower bound is attained if and only if
PPT Slide
Lager Image
The upper bound is attained if and only if
PPT Slide
Lager Image
Proof . Since T is a tree with n > 2 vertices, it has at least two pendant vertices and so, by lemma 1.1, 2 ≼ irr ( T ). On the other hand, it is not difficult to check that for each uv E ( T ), | deg ( u ) − deg ( v )| ≼ n − 2 and E ( T ) = n − 1. So, irr ( T ) ≼ ( n − 1)( n − 2). Notice that Sn is the unique graph with n − 2 as difference of degrees between adjacent vertices. But by Lemma 1.1, Pn is the unique tree that its third Zagreb index is equal to 2, as desired.
2. Main results
The join G = G 1 + G 2 , Figure 1 , 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 union G 1 G 2 together with all the edges joining V 1 and V 2 . For example,
PPT Slide
Lager Image
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 to u 2 ) or ( u 1 = u 2 and v 1 is adjacent to v 2 ) [13] . For instance,
PPT Slide
Lager Image
PPT Slide
Lager Image
The Join of
The Strong product G H , Figure 2 , of graphs G and H has the vertex set V ( G H ) = V ( G ) × V ( H ) and ( a, x )( b, y ) is an edge of G H if a = b and xy E ( H ), or ab E ( G ) and x = y , or ab E ( G ) and xy E ( H ). As an example, Cn K 2 is the closed fence. The tensor product G H , Figure 3 , is defined as 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 ) and u 2 v 2 E ( H )}. For example, Cn P 2 = C 2n . The corona product GoH , Figure 4 , is obtained by taking one copy of G and | V ( G )| copies of H ; and by joining each vertex of the i -th copy of H to the i -th vertex of G , 1 ≤ i ≤ | V ( G )| [19] . For example,
PPT Slide
Lager Image
Finally, for a connected graph G, R ( G ) is a graph obtained from G by adding a new vertex corresponding to each edge of G , then joining each new vertex to the end vertices of the corresponding edge [21] . For example, we can see R ( P 2 ) = K 3 .
PPT Slide
Lager Image
The Strong Product of C5 and K2.
PPT Slide
Lager Image
The Tensor Product of Two Graphs.
PPT Slide
Lager Image
The Corona Product of Two Graphs.
It is well-known that the Cartesian product of graphs can be recognized efficiently, in time O ( mlogn ) for a graph with n vertices and m edges [22] . This operation is commutative and associative as an operation on isomorphism classes of graphs, but it is not commutative. The Cartesian product is not a product in the category of graphs, but the tensor product is the categorical product.
Suppose G and H are graphs with disjoint vertex sets. Following Došslić [8] , for given vertices y V ( G ) and z V ( H ) a splice of G and H by vertices y and z , ( G · H )( y; z ), is defined by identifying the vertices y and z in the union of G and H . Similarly, a link of G and H by vertices y and z is defined as the graph ( G H )( y; z ) obtained by joining y and z by an edge in the union of these graphs. Let H is a tree of progressive degree p and generation r that whose root vertex is r 1 . Also, let DDp,r be the graph of the regular dicentric dendrimer, Figure 6 . So, it is clear that DDp,r = ( H H )( r 1 ; r 1 ).
PPT Slide
Lager Image
The Molecular Graph of Octanitrocubane.
PPT Slide
Lager Image
Regular Dicentric (DD2.4) Dendrimer.
Lemma 2.1. Suppose G and H are rooted graphs with respect to the rooted vertices of a and b, respectively. Then
PPT Slide
Lager Image
and the upper bound is attained if and only if for every vertex u V ( G ) that ua E ( G ), degG ( a ) ≽ degG ( u ) and for every vertex v V ( H ) that vb E ( H ), degH ( b ) ≽ degH ( v ). Moreover, the lower bound is attained if and only if for each edge au E ( G ), degG ( u ) − degG ( a ) ≽ degH ( b ) and for each edge bv E ( H ), degH ( v ) − degH ( b ) ≽ degG ( a ).
Proof . This follows immediately from the definition of splice of two graphs.
In a similar way, by definition of link of two graphs, we have:
Lemma 2.2. Suppose G and H are rooted graphs with respect to the rooted vertices of a and b, respectively. Then
PPT Slide
Lager Image
and the upper bound is attained if and only if for every vertex u V ( G ) that ua E ( G ), degG ( a ) ≽ degG ( u ) and for every vertex v V ( H ) that vb E ( H ), degH ( b ) ≽ degH ( v ). Moreover, the lower bound is attained if and only if for every vertex u V ( G ) that ua E ( G ), degG ( a ) < degG ( u ) and for every vertex v V ( H ) that vb E ( H ), degH ( b ) < degH ( v ).
Lemma 2.3. Let G be a connected graph. Then irr ( G ) = 0 if and only if G is regular.
The line graph L ( G ) of a graph G is defined as follows: each vertex of L ( G ) represents an edge of G , and any two vertices of L ( G ) are adjacent if and only if their corresponding edges share a common endpoint in G [21] .
Lemma 2.4. Let G be a connected graph. Then irr ( L ( S ( G ))) = irr ( G ).
Proof . We assume that uv is an edge of L ( G ) that u and v are vertices corresponding to edges wx and wy of G , respectively. Then | deg L(G) ( u )− deg L(G) ( v )| = | degG ( x ) − degG ( y )|. To compute the third Zagreb index of L ( G ), it is enough to calculate the summation of all degree differences of vertices of distance 2 in L ( G ). Therefore, irr ( L ( S ( G ))) = irr ( G ).
In the next result, the relationship between strong and tensor products of two graphs under the third Zagreb index is investigated.
Lemma 2.5. Let G and H be graphs. Then
PPT Slide
Lager Image
Proof . The summation of | deg GH ( u ) − deg GH ( v )| over all edges ( a, x )( b, y ) such that ( a = b and xy E ( H )) or ( x = y and ab E ( G )), is equal to:
PPT Slide
Lager Image
On the other hand, for each edge ( a, x )( b, y ) of G H that ab E ( G ) and xy E ( H ), we have:
PPT Slide
Lager Image
and hence
PPT Slide
Lager Image
which completes the proof.
Lemma 2.6. Let G and H be two connected graphs. Then
PPT Slide
Lager Image
Proof . Let Hi be the i -th copy of H , 1 ≤ i ≤ | V ( G )|, and let G′ be the copy of G in GoH . We partition edges of GoH into the following three subsets:
  • A= {uv∈E(GoH) |u, v∈V(Hi),i= 1, 2, ..., |V(G)|},
  • B= {uv∈E(GoH) |u, v∈V(G′)},
  • C= {uv∈E(GoH) |u∈V(G′),v∈V(Hi), i = 1, 2, ..., |V(G)|}.
If u′ v′ A , then degGoH ( u′ ) = degH ( u ) + 1 and degGoH ( v′ ) = degH ( v ) + 1 that u′ , v′ V ( Hi ) are corresponding to u, v V ( H ), respectively. Thus | degGoH ( u′ ) − degGoH ( v′ )| = | degH ( u ) − degH ( v )|. Since | V ( G )| edges u′ v′ in E ( GoH ) are corresponding to each edge uv E ( H ), irr 1 = Σ uvA | degGoH ( u )− degGoH ( v )| = | V ( G )| irr ( H ).
It is clear that for each u′ v′ B, degGoH ( u′ ) = degG ( u ) + | V ( H )| and degGoH ( v′ ) = degG ( v ) + | V ( H )|, where u′ , v′ V ( G′ ) are corresponding to u, v V ( G ), respectively. Hence irr 2 = Σ uvB | degGoH ( u ) − degGoH ( v )| = irr ( G ).
Finally, if u′ v′ C , then degGoH ( u′ ) = degG ( u ) + | V ( H )| and degGoH ( v′ ) = degH ( v ) + 1, where u′ V ( G′ ); v′ V ( Hi ) are corresponding to u V ( G ), v V ( H ), respectively. Hence | degGoH ( u′ ) − degGoH ( v′ )| = degG ( u ) + | V ( H )| − degH ( v ) − 1. Consequently,
PPT Slide
Lager Image
By summation of irr 1 , irr 2 and irr 3 , the result can be proved.
As in the proof of Lemma 2.6, | degGoH ( u′ )− degGoH ( v′ )| = degG ( u )+| V ( H )|− degH ( v ) − 1, where for each edge u′ v′ E ( GoH ), vertices u′ V ( G′ ) and v′ V ( Hi ) are corresponding to u V ( G ) and v V ( H ), respectively. Thus,
PPT Slide
Lager Image
Corollary 2.7. Let G and H be two connected graphs. Then
PPT Slide
Lager Image
and the upper bound is attained if and only if H is a tree and
PPT Slide
Lager Image
Moreover, the lower bound is attained if and only if G is a tree and
PPT Slide
Lager Image
Let Gi = ( Vi , Ei ) be N graphs with each vertex set Vi , 1 ≤ i N , having a distinguished or root vertex, labeled 0. The hierarchical product H = GN ⊓ ... ⊓ G 2 G 1 is the graph with vertices the N −tuples xN ... x 3 x 2 x 1 , xi Vi , and edges defined by the adjacencies:
PPT Slide
Lager Image
We encourage the reader to consult [5 , 6] for the mathematical properties of this new graph operation.
Lemma 2.8. Let G and H be connected rooted graphs and r is the root vertex of H. Then
PPT Slide
Lager Image
The upper bound is attained if and only if for each ur E ( H ), degH ( r ) ≽ degH ( u ). Moreover, the lower bound is attained if and only if for each ur E ( H ) and v V ( G ), degH ( r ) + degG ( v ) ≼ degH ( u ).
Proof . Let ur E ( H ) and v V ( G ), then ( v, r )( v, u ) ∈ E ( G H ) and so
PPT Slide
Lager Image
Consequently, if degH ( r ) ≽ degH ( u ) then | deg G H (( v, r )) − deg G H (( v, u ))| = ( degH ( r ) − degH ( u )) + degG ( v ) and if degH ( r ) + degG ( v ) ≼ degH ( u ) then | deg G H (( v, r ))− deg G H (( v, u ))| = ( degH ( u ) − degH ( r ))− degG ( v ). On the other hand for each edge ( u, r )( v, r ) of G H that uv E ( G ), we have | deg G H (( u, r ))− deg G H (( v, r ))| = | degG ( u ) − degG ( v )| and for each edge ( w, u )( w, v ) of G H that u v r , we have | deg G H (( w, u )) − deg G H (( w, v ))| = | degH ( u ) − degH ( v )|, which proves the result.
In what follows, let
PPT Slide
Lager Image
for each i, j ∈ {0, 1, 2, ...}, that i j = 1. Let G 1 , G 2 ,..., Gn be connected rooted graphs with root vertices r 1 , r 2 ,..., rn , respectively. We set
PPT Slide
Lager Image
Also, if G = Gn ⊓ ... ⊓ G 2 G 1 then we will use degG ( r ) to denote deg G1 ( r 1 ) + deg G 1 ( r 2 ) + ... + degGn ( rn ).
Corollary 2.9. Let G 1 , G 2 , ..., Gn be connected rooted graphs with root vertices r 1 , r 1 , ..., rn, respectively. Then
PPT Slide
Lager Image
The upper bound is attained if and only if for each uri E ( Gi ), degGi ( ri ) ≽ degGi ( u ), i = 1, 2, ..., n − 1. Moreover, the lower bound is attained if and only if for each uri E ( Gi ) and v V ( Gi ),
PPT Slide
Lager Image
i = 1, 2, ..., n − 1, j = i + 1, i + 2, ..., n .
Proof . Use induction on n . By Lemma 2.8, the result is valid for n = 2. Let n ≽ 3 and assume the result holds for n . Set G = Gn ⊓ ... ⊓ G 2 G 1 . Thus G n +1 ⊓ ... ⊓ G 2 G 1 = G n +1 G . Then by our assumption,
PPT Slide
Lager Image
On the other hand, again by our assumption,
PPT Slide
Lager Image
which completes our argument.
Example 2.10. Octanitrocubane is the most powerful chemical explosive with formula C 8 ( NO 2 ) 8 ), Figure 5 . Let Γ be the graph of this molecule. Then obviously Γ = Q 3 P 2 . If r is the root vertex of P 2 , one can easily see that
PPT Slide
Lager Image
and for each
PPT Slide
Lager Image
and so, by Lemma 2.8, we have
PPT Slide
Lager Image
Example 2.11. Dendrimers are branched molecules have a high degree of molecular uniformity. The molecular graph of this molecules is constructed from a core and some branches connecting to the core. Let DDp,r be the graph of the regular dicentric dendrimer, see [7] for more information. Then DDp,r = P 2 H , where H is a tree of progressive degree p and generation r , Figure 6 . One can see that irr ( P 2 ) = 0, irr ( H ) = p r+1 + p , and for each ur E ( H ) and
PPT Slide
Lager Image
Therefore, by Lemma 2.8, we have:
PPT Slide
Lager Image
Example 2.12. Consider the graph S 4 whose root vertex is 0. If
PPT Slide
Lager Image
then by Lemma 2.8 we have:
PPT Slide
Lager Image
and if
PPT Slide
Lager Image
then again by Lemma 2.8 we have:
PPT Slide
Lager Image
Lemma 2.13. Let G and H be connected graphs. Then
  • (1)If G is regular, then we have irr(G[H]) = |E(G)|irr(2H) + (|V(G)| − 2|E(G)|)irr(H).
  • (2)If H is regular, then irr(G[H]) = |V(H)|3irr(G).
Proof . 1). Let G be regular. Clearly, for each vertex ( u, v ) ∈ V ( G [ H ]), degG [H] (( u, v )) = | V ( H )| degG ( u ) + degH ( v ). Since G is regular, for each edge ( u, x )( v, y ) ∈ G [ H ] that uv E ( G ), we have | deg G[H] (( u, x ))− deg G[H] (( v, y ))| = | degH ( x ) − degH ( y )| and for every edge ( u, x )( u, y ) that xy E ( H ), we have | deg G[H] (( u, x ))− deg G[H] (( u, y ))| = | degH ( x )− degH ( y )|, which proves the result.
2). Let H be regular. Then for every edge ( u, x )( u, y ) that xy E ( H ), we have | deg G[H] (( u, x ))− deg G[H] (( u, y ))| = 0 and for every edge ( u, x )( v, y ) of G [ H ] that uv E ( G ), we have | deg G[H] (( u, x ))− deg G[H] (( v, y ))| = | V ( H )|| degG ( u )− degG ( v )|. On the other hand, to each edge uv E ( G ), there correspond | V ( H )| 2 edges ( u, x )( v, y ) in E ( GoH ), so irr ( G [ H ]) = | V ( H )| 3 irr ( G ).
Acknowledgements
The authors are indebted to anonymous referees for their suggestions and helpful remarks.
BIO
Mostafa Tavakoli was born in Isfahan, Iran in 1986. He received his M.Sc. from University of Tehran under the direction of Hassan Yousefi-Azari. He is currently a Ph.D candidate at Ferdowsi University of Mashhad. His research interests focus on metric graph theory and mathematical chemistry.
Department of Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad 91775, Iran.
e-mail:M.Tavakoly@ut.ac.ir,Mostafa Tavakoli@ymail.com
Fereydon Rahbarnia received M.Sc. from Boston College, and Ph.D. from Ferdowsi University of Mashhad. He is currently an assistant professor at Ferdowsi University of Mashhad.
Department of Mathematics, Ferdowsi University of Mashhad, P. O. Box 1159, Mashhad 91775, Iran.
e-mail:Rahbarnia@ferdowsi.um.ac.ir
Ali Reza Ashrafi was born in Tehran, Iran in 1964. He received his BSc from Teacher Training University of Tehran, MSc from Shahid Beheshti University and Ph.D at the University of Tehran under the direction of Mohammad Reza Darafsheh. Since 1996 he has been at the University of Kashan. He is now a professor of mathematics and supervised more than fifty MSc students in the field of computational group theory, graph theory and mathematical chemistry. In 2010, he elected as one of the best Iranian scientists in basic sciences. His research interests focus on computational group theory, metric graph theory and mathematical chemistry.
Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317-51167, I. R. Iran.
e-mail:ashrafi@kashanu.ac.ir
References
Abdo H. , Dimitrov D. The total irregularity of graphs under graph operations, to appear in Discussiones Mathematicae Graph Theory.
Albertson M.O. (1997) The irregularity of a graph Ars Combin 46 219 - 225
Astaneh-Asl A. , Fath-Tabar G.H. (2011) Computing the First and Third Zagreb Polynomials of Cartesian Product of Graphs Iranian J. Math. Chem. 2 73 - 78
Aurenhammer F. , Hagauer J. , Imrich W. (1992) Cartesian graph factorization at logarithmic cost per edge Comput. Complexity 2 (4) 331 - 349    DOI : 10.1007/BF01200428
Barriére L. , Comellas F. , Dafló C. , Fiol M.A. (2009) The hierarchical product of graphs Discrete Appl. Math. 157 36 - 48    DOI : 10.1016/j.dam.2008.04.018
Barriére L. , Dafló C. , Fiol M.A. , Mitjana M. (2009) The generalized hierarchical product of graphs Discrete Math. 309 3871 - 3881    DOI : 10.1016/j.disc.2008.10.028
Diudea M.V. , Parv B. (1995) Molecular Topology. 25. Hyper-Wiener index of dendrimers MATCH Commun. Math. Comput. Chem. 32 71 - 83
Došlić T. (2008) Vertex-Weighted Wiener polynomials for composite graphs Ars Math. Contemp. 1 66 - 80
Fath-Tabar G.H. (2011) Old and new Zagreb index MATCH Commun. Math. Comput. Chem. 65 79 - 84
Gutman I. , Trinajstić N. (1972) Graph theory and molecular orbitals,Total π-electron energy of alternant hydrocarbons Chem. Phys. Lett. 17 535 - 538    DOI : 10.1016/0009-2614(72)85099-1
Gutman I. , Das K.C. (2004) The first Zagreb index 30 years after MATCH Commun. Math.Comput. Chem. 50 83 - 92
Gutman I. , Hansen P. , Mélot H. (2005) Variable neighborhood search for extremal graphs. 10. Comparison of irregularity indices for chemical trees J. Chem. Inf. Model. 45 222 - 230    DOI : 10.1021/ci0342775
Hammack R. , Imrich W. , Klavžar S. 2011 Handbook of Product Graphs 2nd ed. Taylor & Francis Group
Hansen P. , Mélot H. (2005) Variable neighborhood search for extremal graphs. 9. Bounding the irregularity of a graph DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 69 253 - 264
Henning M.A. , Rautenbach D. (2007) On the irregularity of bipartite graphs Discrete Math. 307 1467 - 1472    DOI : 10.1016/j.disc.2006.09.038
Hossein-Zadeh S. , Hamzeh A. , Ashrafi A.R. (2010) Extremal properties of Zagreb conindices and degree distance of graphs Miskolc Math. Notes 11 (2) 129 - 137
Khalifeh M.H. , Yousefi-Azari H. , Ashrafi A.R. (2009) The first and second Zagreb indices of some graph operations Discrete Appl. Math. 157 804 - 811    DOI : 10.1016/j.dam.2008.06.015
Luo W. , Zhou B. (2010) On the irregularity of trees and unicyclic graphs with given matching number Util. Math. 83 141 - 147
Stevanović D. (2001) Hosoya polynomial of composite graphs Discrete Math. 235 237 - 244    DOI : 10.1016/S0012-365X(00)00277-6
Tavakoli M. , Rahbarnia F. , Mirzavaziri M. , Ashrafi A.R. , Gutman I. (2013) Extremely irregular graphs Kragujevac J. Math. 37 (1) 135 - 139
Yan W. , Yang B.-Y , Yeh Y.-N (2007) The behavior of Wiener indices and polynomials of graphs under five graph decorations Appl. Math. Lett. 20 290 - 295    DOI : 10.1016/j.aml.2006.04.010
Zhou B. , Luo W. (2008) On irregularity of graphs Ars Combin. 88 55 - 64