Multicenter Wiener indices and their applications J. Serb. Chem. Soc. 80 (8) 1009–1017 (2015) UDC 539.6+544.131 JSCS–4776 Original scientific paper 1009 Multicenter Wiener indices and their applications IVAN GUTMAN1,2*#, BORIS FURTULA1# and XUELIANG LI3 1Faculty of Science, University of Kragujevac, P. O. Box 60, 34000 Kragujevac, Serbia, 2State University of Novi Pazar, Novi Pazar, Serbia and 3Center for Combinatorics, Nankai University, Tianjin, 300071, China (Received 26 January, revised 12 February, accepted 13 February 2015) Abstract: The Wiener index W could be viewed as a molecular structure des- criptor composed of increments representing interactions between pairs of atoms. A generalization of the W are the Steiner–Wiener indices kW , k = 3, 4,… In the quantity kW , interactions between k-tuples of atoms play a role, based on the concept of the Steiner distance. It is shown that the term kW Wλ+ provides an approximation for the boiling points of alkanes better than W itself. The best such approximation is obtained for 7k = . Keywords: Wiener index; multicenter Wiener index; Steiner distance; Steiner– –Wiener index; molecular graph. INTRODUCTION The Wiener index (W) is one of the oldest and most examined graph-based molecular structure descriptors. Details on its mathematical properties and che- mical applications are given in reviews,1–5 recent research papers,6–9 and the references cited therein. On the occasion of the fiftieth anniversary of the Wiener index, three special journal issues were published.10–12 Additional historical data on W can be found in a survey.13 The Wiener index is defined in the following manner. Let G be a molecular graph and 1 2, , , nv v v be its vertices. The distance between the vertices iv and jv , denoted by ( , )i jd v v , is the number of edges in (= the length of) the shortest path that connects iv and jv . Then: ( ) ( , )i j i j W W G d v v < = =  (1) with the summation embracing all pairs of vertices (vi,vj) of the molecular graph G. * Corresponding author. E-mail: gutman@kg.ac.rs # Serbian Chemical Society member. doi: 10.2298/JSC150126015G _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ 1010 GUTMAN, FURTULA and LI Bearing in mind that each vertex of the molecular graph represents an atom of the underlying molecule,14 the quantity W, defined by means of Eq. (1), may be viewed as a sum of structural increments representing pairs of atoms, i.e., two- -center interatomic interactions. From this point of view, one could think of three-center, four-center, etc. interactions that would lead to the following evident multicenter extension of the Wiener-index concept: 3 3 ( ) ( , , )i j k i j k W W G d v v v < < = =  (2) 4 4 ( ) ( , , , )i j k l i j k l W W G d v v v v < < < = =  (3) 5 5 ( ) ( , , , , )i j k l m i j k l m W W G d v v v v v < < < < = =  (4) etc. In formulas (2)–(4), the meaning of the three-, four-, five-vertex distances requires clarification. In fact, a long time ago, Chartrand et al. introduced such a multi-vertex distance into graph theory,15 which was eventually much studied under the name “Steiner distance”.16 Its definition is given in the subsequent section. The multicenter Wiener-type indices based on the Steiner distance will be referred to as “Steiner–Wiener indices” and are defined in the subsequent section. The present work is aimed at establishing their chemical applicability. STEINER DISTANCE AND STEINER–WIENER INDEX Let G be a connected graph with n vertices. Let 1 2 { , , , } ki i i S v v v=  be a set of k distinct vertices of G. Then the Steiner tree, ( )T S , is a tree (= connected acyclic graph) that is a subgraph of G, containing all vertices of S, and possessing a minimal number of edges. The number of edges of ( )T S is the Steiner distance of the vertices 1 2 , , , ki i i v v v . For details on the Steiner-distance concept, see elsewhere.17,18 For 2,3, ,k n=  , the k-th Steiner–Wiener index of the (molecular) graph G is defined as: 1 2 ( ) ( , , , ) kk k i i i S W W G d v v v= =   (5) where the summation goes over all k-element subsets 1 2 { , , , } ki i i S v v v=  of the vertex set of G. Steiner–Wiener indices, kW , were recently considered, 19 and their basic mathematical properties determined. Some of these are the following: 1. 2 ( )W G coincides with the ordinary Wiener index ( )W G , Eq. (1). 2. Eqs. (2), (3), and (4) are special cases of Eq. (5), for 3k = , 4k = and 5k = , res- pectively. 3. For a graph G with n vertices, if k n= , then ( ) 1kW G n= − . 4. For a graph G with n vertices, if k n> , then ( ) 0kW G = . For a tree T, and for all 2,3, ,k n=  : _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ MULTICENTER WIENER INDICES 1011 1 1 2 1 ( ) ( ) ( ) k k e i n e n e W T i k i − =    =   −    (6) where 1( )n e and 2 ( )n e are the number of vertices lying on the two sides of the edge e, and where the first summation goes over all edges of T. For all edges e of the tree T, 1 2( ) ( )n e n e n+ = . Note that for 2k = , formula (6) reduces to the expression (7), discovered by Wiener himself as early as in 1947:7,14,20 1 2( ) ( ) ( ) e W T n e n e=  (7) STEINER–WIENER INDICES AND BOILING POINTS OF ALKANES The first chemical application of the Wiener index was its usage for the prediction of the normal boiling points of alkanes.20 Eventually, correlations with boiling points became a standard test for the quality of topological indices.21–24 In view of this, this physico-chemical parameter is also used in these studies of the Steiner–Wiener indices. The well known23 plot of the normal boiling points vs. the Wiener index is reproduced in Fig. 1. The curve passing through the data-points is of the form: Fig. 1. Correlation between normal boiling points (bp / K) and Wiener index (W) for the set of all isomeric alkanes with 2 to 9 carbon atoms (74 compounds).25 The curve passing through the data-points is specified by Eq. (8). Statistical data pertaining to this correlation are found in Tables I and II, for k = 2. _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ 1012 GUTMAN, FURTULA and LI * * calc * ( ) 1 a bW bp bp W cW + ≈ = + (8) where *W W= and where , and a b c are fitting parameters. The correlation between the experimental and calculated boiling points (i.e., between bp and calcbp , cf. Eq. (8)), is shown in Fig. 2. TABLE I. Fitting parameters in formulas (8) and (9), for k = 2,3,..., 9. The (a,b,c)-values were obtained by means of the scaled Levenberg–Marquardt algorithm.26 The λ-values are those for which the respective correlation coefficients are maximal, cf. Fig. 3. The parameters for the best approximation are indicated by boldface k a b c λ 2 191.328 15.104 0.031 – 3 192.480 14.547 0.031 0.023 4 193.704 14.820 0.032 0.044 5 191.287 16.476 0.037 0.063 6 186.764 18.773 0.043 0.127 7 181.255 21.421 0.049 0.392 8 180.547 20.834 0.047 0.802 9 187.788 16.790 0.036 1.400 TABLE II. Statistical data for the correlations between boiling points and the topological indices * kW W Wλ= + , k =2,3,..., 9; R = correlation coefficient, ARE = average relative error (in %), MRE = maximal observed relative error (in %). The data for the best approximation are indicated by boldface. For details, see Eqs. (8) and (9) and the text k R ARE MRE 2 0.98954 1.45 8.42 3 0.98957 1.45 8.83 4 0.99018 1.41 9.46 5 0.99135 1.33 8.58 6 0.99256 1.23 6.80 7 0.99323 1.18 4.63 8 0.99273 1.23 4.19 9 0.99149 1.33 6.98 The most obvious idea for testing the Steiner–Wiener indices would be to set * kW W= into Eq. (8). This, however, did not yield any improvement, and thus had to be abandoned. A better option was to modify the Wiener index as: * kW W Wλ= + (9) and use the variable *W in combination with Eq. (8) . For each fixed choice of k, k = 3,4,...8, the parameter λ was varied, and its value determined to maximize the correlation coefficient for the linear correlation between bp and *calc ( )bp W . In all the studied cases, an optimal value for λ exists at which the correlation coefficients attain a maximum; a characteristic example is shown in Fig. 3. _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ MULTICENTER WIENER INDICES 1013 Fig. 2. Correlation between the calculated boiling points ( calcbp , according to Eq. (8), * =W W ) and the experimental boiling points (bp) for the same compounds as in Fig. 1. Statistical data pertaining to this correlation are found in Tables I and II, for k = 2. Fig. 3. The λ-dependence of the correlation coefficient R for the correlation between bp and calcbp for the case 5k = . The maximum is attained at 0.063λ = , cf. Table I. The results thus obtained are presented in Tables I and II, and in Figs. 4 and 5. _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ 1014 GUTMAN, FURTULA and LI Fig. 4. Normal boiling points (bp / K) vs. 7W Wλ+ for the same alkanes as in Fig. 1. As the data in Tables I and II show, the choice 7k = provides the best agreement between bp and bpcalc, cf. Eqs. (8) and (9). Fig. 5. The best correlation between bp and bpcalc, was obtained by Eqs. (8) and (9) for k = 7. Statistical data pertaining to this correlation are to be found in Tables I and II. _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ MULTICENTER WIENER INDICES 1015 DISCUSSION AND CONCLUDING REMARKS Viewing at the Wiener index as a structure descriptor based on two-center interatomic interactions, it could be expected that the next-important structural feature would be three-center interactions. In the case of Steiner–Wiener index applied to alkanes, this certainly cannot be the case, since for trees the following identity holds: 3 2 ( ) ( ) 2 n W T W T − = (10) Therefore, 3W contains the exactly same structural information as the ordi- nary Wiener index, W. Relation (10) is deduced from Eq. (6) as follows. For 3k = , Eq. (6) has the form: 1 2 1 2 3 ( ) ( ) ( ) ( ) ( ) 1 2 2 1 e n e n e n e n e W T        = +               which, bearing in mind that 1 2( ) ( )n e n e n+ = , is transformed into: 2 2 1 1 3 1 2 1 2 1 2 1 2 ( )[ ( ) 1] ( )[ ( ) 1] ( ) ( ) ( ) 2 2 ( ) ( ) 2 2 ( ) ( ) ( ) ( ) 2 2 e e e n e n e n e n e W T n e n e n e n e n n e n e n e n e − − = +   + − − = =    Formula (10) is now obtained from Eq. (7). The calculations fully agree with the above argument: The accuracies of the models for 2k = and 3k = were the same, see Table I. If 3k > , because of the very large number of k-tuples of vertices, the calculation of the Steiner–Wiener index kW based on its definition (5) becomes extremely cumbersome. In the case of acyclic systems (such as the molecular graphs of alkanes), instead of Eq. (5), the calculations could be realized using Eq. (6), which is significantly easier. In fact, by means of Eq. (6) any Steiner–Wiener index kW could be calculated just as easily as the ordinary Wiener index W. The fact that the accuracy of the approximations based on the indices * k W W Wλ= + increases with k, and reaches its maximum at 7k = , is some- what unexpected. It may be that this is a statistics-based artifact of the considered models. Nevertheless, this phenomenon deserves further examination. The results of the present study may be considered from a pessimistic and from an optimistic point of view. A pessimist would say that there is very little difference between the Figs. 1 and 4, as well as between Figs. 2 and 5. An optimist would point to the fact that the average and maximal errors of the best _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ 1016 GUTMAN, FURTULA and LI model (based on 7W Wλ+ ) are, respectively, by 20 and 50 % smaller than those of the starting model (based solely on W). In view of this, it may be concluded that by adding multicenter distance-contributions to the Wiener index, its appli- cability to model physicochemical properties of alkanes is improved, but only to a limited extent. И З В О Д ВИШЕЦЕНТРИЧНИ ВИНЕРОВИ ИНДЕКСИ И ЊИХОВЕ ПРИМЕНЕ ИВАН ГУТМАН1,2, БОРИС ФУРТУЛА1 и XUELIANG LI3 1Природно–математички факултет Универзитета у Крагујевцу, 2Државни универзитет у Новом Пазару и 3Center for Combinatorics, Nankai University, Tianjin, China Винеров индекс W се може посматрати као молекулски структурни дескриптор сас- тављен од сабирака који репрезентују интеракције између парова атома. Једна генерали- зација Винеровог индекса су Штајнер–Винерови индекси Wk, k = 3,4,... У индексу Wk се води рачуна о интеракцијама k атома, заснованих на појму Штајнеровог растојања. Показано је да формула W+λWk омогућава апроксимативно израчунавање тачке кљу- чања алкана боље него сам Винеров индекс. Најбоља таква апроксимације је за k = 7. (Примљено 26. јануара, ревидирано 12. фебруара, прихваћено 13. фебруара 2015) REFERENCES 1. I. Gutman, Y. N. Yeh, S. L. Lee, Y. L. Luo, Indian J. Chem., A 32 (1993) 651 2. S. Nikolić, N. Trinajstić, Z. Mihalić, Croat. Chim. Acta 68 (1995) 105 3. D. H. Rouvray, in Topology in Chemistry – Discrete Mathematics of Molecules, D. H. Rouvray, R. B. King, Eds., Horwood, Chichester, 2002, p. 16 4. K. Xu, M. Liu, K. C. Das, I. Gutman, B. Furtula, MATCH Commun. Math. Comput. Chem. 71 (2014) 461 5. M. Liu, B. Liu, MATCH Commun. Math. Comput. Chem. 69 (2013) 491 6. A. Hamzeh, S. Hossein-Zadeh, A. R. Ashrafi, MATCH Commun. Math. Comput. Chem. 69 (2013) 47 7. R. Škrekovski, I. Gutman, MATCH Commun. Math. Comput. Chem. 72 (2014) 295 8. H. Lin, MATCH Commun. Math. Comput. Chem. 72 (2014) 783 9. K. Hrinakova, M. Knor, R. Škrekovski, A. Tepeh, MATCH Commun. Math. Comput. Chem. 72 (2014) 791 10. 50th Anniversary of the Wiener Index, I. Gutman, S. Klavžar, B. Mohar, Eds., Discr. Appl. Math. 80 (1997), pp. 1–113 11. Fifty Years of the Wiener Index, I. Gutman, S. Klavžar, B. Mohar, Eds., MATCH Commun. Math. Comput. Chem. 35 (1997), pp. 1–259 12. Fifty Years of the Wiener Index, I. Gutman, Ed., J. Serb. Chem. Soc. 62 (1997), pp. 185– –294 13. D. H. Rouvray, in Topology in Chemistry – Discrete Mathematics of Molecules, D. H. Rouvray, R. B. King, Eds., Horwood, Chichester, 2002, p. 1 14. I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, Germany, 1986 15. G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou, Časopis Pest. Mat. 114 (1989) 399 16. Jakob Steiner (1795–1863), Swiss mathematician _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ MULTICENTER WIENER INDICES 1017 17. F. K. Hwang, D. S. Richards, P. Winter, The Steiner Tree Problem, North-Holland, Amsterdam, 1992 18. W. Goddard, O. R. Oellermann, in: Structural Analysis of Complex Networks, M. Dehmer, Ed., Birkhäuser, Dordrecht, 2011, pp. 49–72 19. X. Li, Y. Mao, I. Gutman, Discuss. Math. Graph Theory, in press 20. H. Wiener, J. Am. Chem. Soc. 69 (1947) 17 21. D. H. Rouvray, J. Comput. Chem. 8 (1987) 470 22. P. G. Seybold, M. May, U. A. Bagal, J. Chem. Educ. 64 (1987) 575 23. Z. Mihalić, N. Trinajstić, J. Chem. Educ. 69 (1992) 701 24. G. Rücker, C. Rücker, J. Chem. Inf. Comput. Sci. 39 (1999) 788 25. R. L. Brown, S. E. Stein, in: NIST Standard Reference Database No. 69, P. J. Linstrom, W. G. Mallard, Eds., Gaithersburg, MD, 2014, http://webbook.nist.gov 26. J. Nocedal, S. J. Wright, Numerical Optimization, Springer, New York, 2006. _________________________________________________________________________________________________________________________ (CC) 2015 SCS. All rights reserved. Available on line at www.shd.org.rs/JSCS/ << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA /BGR /CHS /CHT /CZE /DAN /DEU /ESP /ETI /FRA /GRE /HEB /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN /ITA /JPN /KOR /LTH /LVI /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR /POL /PTB /RUM /RUS /SKY /SLV /SUO /SVE /TUR /UKR /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice