IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 49 (2011), 1154 ISSN 2232-2094 BOUNDS ON GUTMAN INDEX Vesna Andova Darko Dimitrov Jin Fink Riste Skrekovski Ljubljana, June 23, 2011 Bounds on Gutman Index Vesna Andovaa, Darko Dimitrov61, Jiri Finkc2, Riste Skrekovski^3 aInstitute of Mathematics and Physics, Faculty of Electrical Engineering and Information Technologies, Ss Cyril and Methodius Univ., Ruger Boskovik, P. O. Box 574, 1000 Skopje, Macedonia E-mail: vesna.andova@gmail.com bInstitut fur Informatik, Freie Universitat Berlin, Takustrafie 9, D-14195 Berlin, Germany E-mail: darko@mi.fu-berlin.de cDepartment of Applied Mathematics, Faculty of Mathematics and Physics, Charles University CO Malostranske namestz 25, 118 00 Prague 1, Czech Republic E-mail: fink@kam.mff.cuni.cz £ CO CO w CD ■ i J-H dDepartment of Mathematics, University of Ljubljana, Jadranska 21, 1111 Ljubljana, Slovenia E-mail: skrekovski@gmail.com (Received May 4, 2011) Abstract The Gutman index (also known as Schultz index of the second kind) of a graph G is defined as Gut(G) = j2uvev(g) d(u)d(v)d(u,v). We show that among all graphs on n vertices, the star graph Sn has minimal Gutman index. In addition, we present upper and lower bounds on Gutman index for graphs with minimal and graphs with maximal Gutman index. 1 Corresponding author 2Supported by project 1M0545 of the Czech Ministry of Education and by the CZ-SL bilateral project MEB 090805. 3Supported by the CZ-SL bilateral project MEB 090805. 1 Introduction The Wiener index, W(G) = £MveV(G) d(u,v), of a connected graph G is a graph invariant much studied in both mathematical and chemical literature; for details see the reviews [1, 4, 6, 9, 10, 11]. In this paper we are concerned with a variant of the Wiener index called the Schultz index of the second kind [9], but for which fi the name Gutman index has also been used [12]. Throughout this paper, the latter o fi CO name is used. Another variant of Wiener index is the edge-Wiener index, defined as the sum of the distances between all pairs of edges of a connected graph G, i.e., We(G) = £ e,f£E(G) d(e,f); where the distance between two edges is the distance between the corresponding vertices in the line graph of G. For a vertex v E V(G), we denote by dG (v) the degree of v in G. For the sake of simplicity, we write d(v) if the graph G is clear from the context. The minimum vertex degree of a graph G we denote by 8 = 5(G), and the maximum degree we denote by A = A(G). For v,u E V(G), we denote by dG(u,v) (or simply d(u,v)) the length of a shortest path in G between u and v. The Gutman index of a connected graph G is defined as Gut(G) = ^ d(u)d(v)d(u,v). u,veV (G) The Gutman index of graphs attracts attention just recently. Dankelmann et al. [3] presented an asymptotic upper bound for the Gutman index and also established the relation between the edge-Wiener index and Gutman index of graphs. Chen and Liu studied the maximal and minimal Gutman index of unicyclic graphs [2], and maximal Gutman index of bicyclic graphs was determined by Feng and Liu [8]. Gutman [9] gave the following relation between the Gutman and the Wiener index for a tree T m CD i u on n vertices Gut(T) = 4W(T) - (2n - 1)(n - 1). (1) i Jh In [5] lower and upper bounds for the Wiener index for a graph G on n vertices were CD given. Namely, there it was shown that n) = W(Kn) < W(G) < W(Pn) = [n + r), (2) where Kn and Pn are the complete graph and path, respectively, on n vertices. The complete bipartite graph Ki,n-i is called a star, denote by Sn. A tree T is a complete k-regular if every vertex has degree 1 or k. The diameter of a graph G is defined as diam(G) = maxu,veV(G) d(u,v). A tree where all leaves are on the same distance to the root is called a balanced tree. CD Here, we present upper and lower bounds on the Gutman index, we prove that 2 £ CO CO among all connected graphs on n vertices a star, Sn, has minimal Gutman index, and a path, Pn, has maximal Gutman index. We also determine bound of Gutman index for a connected graph with bounded minimum or maximum degree. 2 The graph with minimal Gutman index First, we show a general lower bound on Gutman index. o Theorem 2.1. For every connected graph G on n vertices, it holds that i (2n - 3)(n - 1) = Gut(Sn) < Gut(G). The equality holds if and only if G is star Sn. Proof. First, consider the case when G has no leaves, i.e., 8(G) > 2. Then, Gut(G) = £ d(u)d(v)d(u, v) > 4 £ d(u,v) u,veV(G) u,veV(G) > 4^^ = 2n(n - 1) > (2n - 3)(n - 1) = Gut(Sn). The case when 8(G) = 1, we prove by induction on the number of vertices. For CD n =1 the claim of the proposition is obvious. Assume that the theorem holds for a graph G on n vertices. We construct a graph G' on n + 1 vertices from G by adding a leaf x incident to a E V(G). We show that by adding x, the Gutman index increases by at least 4n - 3 = Gut(Sn+1) - Gut(Sn). To simplify the exposition of the proof, let DG(u,v) = dG(u)dG(v)dG(u, v), and CSI 2 w CD fi CD W U a CD fi similarly DG' (u, v) = dG'(u)dG'(v)dG' (u,v). Gut(G') - Gut(G) = Y [Dc(a, v) - DG(a,v)]+ £ DG,(x,v) v€V(G)\{a} v€V(G) + E [D G'(u, v) - Dc(u,v)]. «,»ev (G)\{a} CD From the construction of the graph G', it is obvious that dG' (u, v) = dG(u, v), and dG'(x,v) = 1 + dG(a,v) for every u,v G V(G). Also notice that the degree of a increases by 1, but all the other vertex degrees are not changed. It is clear that the contribution of u,v G V(G) \ {a} is the same in Gut(G') and in Gut(G). Hence Gut(G') - Gut(G) = Y dG(v)dG(a,v) + £ dG'(v)(dG(a} v) + 1) v€V(G)\{a} vev(G) = 2 £ dG (v)dG(a,v) + £ dG (v) + 1. v€V(G)\{a} vev(G) Since dG(a,v) > 1 and dG(v) > 1 for every v G V(G) \ {a} and Y1 veV(G) dG(v) o 2|E(G)| > 2(n - 1), we infer Gut(G') - Gut(G) > 4n - 3. Moreover the equality holds if and only if dG(v) = 1 for every v G V(G) \ {a}, which satisfies only the star Sn. □ C^ From (1) and (2) we find that for every tree T on n vertices Gut(T) < O(n3). Together with Theorem 2.1, we obtain the following result. Corollary 2.1. For every tree T on n vertices, it holds that ^ (n - 1)(2n - 3) = Gut(Sn) < Gut(T) < Gut(Pn) = (n - 1)(2n3 - 4n + 3). 3 Bounds on graphs with minimal Gutman index In this section, we consider graphs with minimal Gutman index. First, we show lower and upper bounds for graphs with minimum degree at least two. Proposition 3.1. A connected graph G on n vertices with minimum degree at least 5 > 2 and minimal Gutman index satisfies 52n 5(5 + 1)n2 > Gut(G) > -^(2n - 5 - 2). Proof. First, we show the lower bound csi 1 n Gut(G) = - > d(u) > d(v) d(u,v) >— mini d(u) > d(v) d(u,v) 2 ^^ ^^ 2 u * u v nS ( „ , v- „ A > —— mm I d(u) d(u, vn . \ / CO CO - 2 Since there are d(u) vertices on distance one to u, and n — d(u) — 1 vertices on distance at least two to u, we have further nS / \ nS Gut(G) > — min d(u)(d(u) + 2(n — d(u) — 1)) = — min ( d(u)(2n — d(u) — 2) o fi 2 u 2 u The quadratic function f (x) = x(2n — x — 2) with S < x < n — 1 has its minimum at S. Thus, n S Gut(G) > — S(2n — S — 2). o 2 Now, we show the upper bound. By Erdos-Gallai theorem [7], there exist a graph H on n — 1 vertices such that (a) all its vertices are of degree S — 1 if S or n is odd; or (b) a vertex x is of degree S and all others are of degree S — 1 if both S and n are even exists. From H, we construct the graph H* by introducing a new "vertex y adjacent to all vertices of H. Observe that en = |E(H)| = (S — 1) (n — 1) CO of y to Gut(H*) is "in J] dn* (y)dff* (v)dn* (y, v) < (n — 1)((n — 2)S + S + 1). vev (H) fi The contribution of x to Gut(H*) is V dn * (x)dn* (v)dn* (x,v) < (S + 1)(S2 + 2S(n — S — 2)), 2 . The contribution vev (H) and the remaining vertices of H* contribute with 'n - 2 dH * (u)dH * (v)dH * (u,v) = 82 eH - 8 + 2( ( -u,veV (H)\{x} Thus £ dH* (u)dH* (v)dH* (u, v) = 82 eH - 8 + 2 ( [ - eH + 8 j 2 Gut(H*) <(n - 1)((n - 2)8 + 8 + 1) + (8 + 1)(82 + 28(n - 8 - 2)) + 82 eH - 8 + 2( (n2^ - eH + 8 2( %2] - eH + 8 =(n - 1)(n8 - 8 + 1) + (8 + 1)(2n8 - 82 - 48) + 8 <8(8 + 1)n2 - 2(83 + 58 - 2)n - 82(8 + 1) - 38 - 1 i-H 22 <8(8 + 1)n2. O Corollary 3.1. A connected graph G on n vertices with minimum degree at least & 8 > 2 and minimal Gutman index satisfies CS 8(8 + 1)n2 - O(n) > Gut(G) > 82n2 - O(n). Now, we show an upper bound for graphs with minimal Gutman index and maximum degree at most A. CO CO Proposition 3.2. A connected graph G on n vertices with maximum degree at most A > 2 and minimal Gutman index satisfies Gut(G) < 4(n2 - 8n + 4) logA-1 n. Proof. Let G is a A-regular balanced tree on n vertices. If diam(G) = 2k, then n - 1 = A(A - 1) - 1. This tree has A(A - 1)k-1 = (A-2r±2 leaves and A=r inner A - 2 v ; A-1 A-1 vertices. Notice that logA-1 A—2n < k < logA-1 n. CD The tree G has three types of vertex pairs: a pair of two leaves, a leaf and an inner vertex, and a pair of two inner vertices. Their contribution to the Gutman index is: • Two leaves: the distance between two leaves is at most diam(G) = 2k, so their contribution to the Gutman index is at most a & (^ )2k< ( (a a2>'1+2 • A leave and an inner vertex: since every inner vertex has degree A, and the distance between any two vertices is at most 2k, these pairs contribution in the sum is less than (A - 2)n + 2 n - 2 , A 8 a -1 ■ A-r2kA • Two inner vertices: these pair contribute at most a % (?)2kA2 <( A-r)2 A2k Now, ^ /(A - 2)n + 2\ \ (A - 2)n + 2 n - 2„IA (n - 2\2a2i Gut(G) < ^-—t- k + ^-—t----2kA + -- A2k v ; V A - 1 ) A -1 A - 1 VA - 1/ fi =(A4k^(A - 1)2(n2 - 8n + 4) < 4(n2 - 8n + 4)logA-1 n, & o and this proves the upper bound. □ i Note that if G is a graph with maximum degree A < 2, then G is a path. CN 4 Bounds on graphs with maximal Gutman index CO In this section, we consider graphs with maximal Gutman index. First, we show lower HH and upper bounds for graphs with maximum degree at most A. Proposition 4.1. Let G be a connected graph on n vertices with maximum degree A(G) < A, and maximal Gutman index. Then, the following holds: < Gut(G) < . 3 A2 < Gut(G) < ' A2. (n + 1)3 A2 ^ ^ (n + 1 CD }h Proof. For the lower bound we consider the graph Q which is illustrated in Figure 1. To simplify the calculation, we assume that s = (A + 1)3, bn and 3an/(A + 1) are fi integers. The graph Q has n vertices, so 2an + bn = n holds. A pair (x,y), where x is a vertex from QL and y is a vertex from QR, contributes to Gut(Q) at least A2(bn + 1). Since there are an vertices in bough, QL and QR, the contribution of these vertices is (an)2A2(bn + 1). Under the constraint 2a + b = 1, ql Q R L.p—1 KL,P KR,P-i 10 0 fi o 1 CO ^ CO CO KL,P kR,p-2 K kR'3 K L'2 KR'2 Figure 1: The graph Q consist of two identical parts QL and QR connected by path on nb vertices. QL (resp. QR) consists of a lexicographic product Pp [Ks], s = , plus the all edges between the vertices of K^1 and Kf^ (resp. Kf1 and KR,p) except the edge xLyL (resp. xRyR). The vertices xL and yL (resp. xR and yR) are adjacent to the vertex v1 (resp. vbn). the expression (an)2A2(bn + 1) attains maximum for a = (n + 1)/3n and b = n-2• Finally we have Gut(Q) > (n + 1)3 27 A2. Now, we show the upper bound. From (2) and A(G) < A, it follows that Gut(G) < £ A2 d(u, v) = A2W(G) < A2W(Pn) = A2 (n + ^ ii ii S / □ m CD CD m u a CD fi For graphs with bounded maximum degree, we obtain the following result. Corollary 4.1. Let G be a connected graph on n vertices with bounded maximum degree A. Then, O(n3) > Gut(G) > Q(n2logn), and those bounds can be attained. Proof. The lower bound follows directly from Proposition 3.2 and the upper bound from Proposition 4.1. □ io 0 fi o 1 CO ^ CO CO In the sequel, we consider lower and upper bounds for graphs with maximal Gut-man index and minimum degree at least S. Dankelmann et al. [3] presented the following upper bound on Gutman index. Theorem 4.1. (Dankelmann et al. [-3]) Let G be a connected graph on n vertices. Then 24 , * Gut(G) < — n5 + O (n§J , and the coefficient of n5 is the best possible. Now, we present the lower bound. Proposition 4.2. A connected graph G on n vertices with minimum degree at least S, and maximal Gutman index satisfies 55 < Gut(G). Proof. To show the bound consider the graph L given in Figure 2. To simplify the K 25 (n + S — 1)5 55 S5 □ References [1] D. Bonchev, The Wiener number - some applications and new developments, in: D. H. Rouvray, R. B. King (Eds.), Topology in Chemistry - Discrete Mathematics of Molecules, Horwood, Chichester, 2002, pp. 58-88. CD [2] S. B. Chen, W. J. Liu, Extremal modified Schultz index of bicyclic graphs, 2 CO CO m MATCH Commun. Math. Comput. Chem. 64 (2010) 767-782. [3] P. Dankelmann, I. Gutman, S. Mukwembi, H. C. Swart, The edge-Wiener index lO of a graph Gutman, Discrete Math. 309 (2009) 3452-3457. [4] A. A. Dobrynin, R. Entringer, and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249. [5] R. C. Entringer, D. E. Jackson, D. A. Snyder, Distance in graphs, Czech. Math. J. 26 (1976) 283-296. [6] R. C. Entringer, Distance in graphs: trees, J. Combin. Math. Combin. Comput. CO 24 (1997) 65-84. [7] P. Erdos, T. Gallai, Graphs with given degrees of vertices, Mat. Lapok 11 (1960) 264-274. [8] L. Feng, W. Liu, The Maximal Gutman Index of Bicyclic Graphs, MATCH Commun. Math. Comput. Chem. 66 (2011) 699-708. [9] I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci. 34 (1994) 1087-1089. CD ■ i [10] I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986. [11] I. Gutman, Y. Yeh, S. Lee, and Y. Luo, Some recent results in the theory of the Wiener number, Indian J. Chem. 32A (1993) 651-661. [12] R. Todeschini, V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim (2000). [13] H. Hua, Wiener and Schultz molecular topological indices of graphs with specified cut edges, MATCH Commun. Math. Comput. Chem. 61 (2009) 643-651. lO 0 fi o 1 CO ^ CO CO m CD CD m u a CD fi