Abstract
In theoretical chemistry, distance-based molecular structure descriptors are used for modeling physical, pharmacologic, biological and other properties of chemical compounds. We introduce a generalized Wiener polarity index W k (G) as the number of unordered pairs of vertices {u, v} of G such that the shortest distance d (u, v) between u and v is k (this is actually the kth coefficient in the Wiener polynomial). For k = 3, we get standard Wiener polarity index. Furthermore, we generalize the terminal Wiener index TW k (G) as the sum of distances between all pairs of vertices of degree k. For k = 1, we get standard terminal Wiener index. In this paper we describe a linear time algorithm for computing these indices for trees and partial cubes, and characterize extremal trees maximizing the generalized Wiener polarity index and generalized terminal Wiener index among all trees of given order n.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chepoi V., Klavžar S.: The Wiener index and the Szeged index of benzenoid systems in linear time. J. Chem. Inf. Comput. Sci. 37, 752–755 (1997)
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. (2001) Introduction to Algorithms, 2nd edn. MIT Press, Cambridge
Dankelmann P., Gutman I., Mukwembi S., Swart H.C.: The edge-Wiener index of a graph. Discret. Math. 309, 3452–3457 (2009)
Deng H.: On the extremal Wiener polarity index of chemical trees. MATCH Commun. Math. Comput. Chem. 60, 305–314 (2011)
Deng H., Xiao H., Tang F.: The maximum Wiener polarity index of trees with k pendants. Appl. Math. Lett. 23, 710–715 (2010)
Deng H., Xiao H., Tang F.: On the extremal Wiener polarity index of trees with a given diameter. MATCH Commun. Math. Comput. Chem. 63, 257–264 (2010)
Deng, X., Zhang, J.: Equiseparability on terminal Wiener index. In: Goldberg, A.V., Zhou, Y. (eds.) Algorithmic Aspects in Information and Management, pp. 166–174. Springer, Berlin (2009)
Du W., Li X., Shi Y.: Algorithms and extremal problem on Wiener polarity index. MATCH Commun. Math. Comput. Chem. 62, 235–244 (2009)
Dobrynin A.A., Entringer R.C., Gutman I.: Wiener index of trees: theory and applications. Acta Appl. Math. 66, 211–249 (2001)
Gutman I., Furtula B., Petrović M.: Terminal Wiener index. J. Math. Chem. 46, 522–531 (2009)
Gutman I., Polansky O.E.: Mathematical Concepts in Organic Chemistry. Springer, Berlin (1988)
Gutman, I., Zhang, Y., Dehmer, M., Ilić, A.: Altenburg, Wiener, and Hosoya polynomials. In: Gutman, I., Furtula, B. (eds.) Distance in Molecular Graphs—Theory, pp. 49–70. Univerity of Kragujevac, Kragujevac (2012)
Hosoya, H.: Mathematical and chemical analysis of Wiener’s polarity number. In: Rouvray, D.H., King, R.B. (eds.) Topology in Chemistry—Discrete Mathematics of Molecules. Horwood, Chichester (2002)
Hosoya H.: On some counting polynomials in chemistry. Discret. Appl. Math. 19, 239–257 (1988)
Ilić A., Stevanović D.: On Comparing Zagreb Indices. MATCH Commun. Math. Comput. Chem. 62, 681–687 (2009)
Ilić A., Ilić A., Stevanović D.: On the Wiener index and Laplacian coefficients of graphs with given diameter or radius. MATCH Commun. Math. Comput. Chem. 63, 91–100 (2010)
Ilić A., Klavžar S., Stevanović D.: Calculating the degree distance of partial Hamming graphs. MATCH Commun. Math. Comput. Chem. 63, 411–424 (2010)
Imrich W., Klavžar S.: Product Graphs: Structure and Recognition. Wiley, New York (2000)
Klavžar S.: Bird’s eye view of the cut method and a survey of its applications in chemical graph theory. MATCH Commun. Math. Comput. Chem. 60, 255–274 (2008)
Klavžar S., Gutman I.: Wiener number of vertex-weighted graphs and a chemical application. Discret. Appl. Math. 80, 73–81 (1997)
Liu B., Hou H., Huang Y.: On the Wiener polarity index of trees with maximum degree or given number of leaves. Comp. Math. Appl. 60, 2053–2057 (2010)
Nikolić S., Kovačević G., Milićević A., Trinajstić N.: The Zagreb indices 30 years after. Croat. Chem. Acta 76, 113–124 (2003)
Sagan B.E., Yeh Y.N., Zhang P.: The Wiener polynomial of a graph. Int. J. Quantum Chem. 60, 959–969 (1996)
Székely, L.A., Wang, H., Wu, T.: The sum of the distances between the leaves of a tree and the ‘semi-regular’ property. Discret. Math. 311, 1197–1203 (2011). doi:10.1016/j.disc.2010.06.005
Todeschini R., Consonni V.: Handbook of Molecular Descriptors. Wiley, Weinheim (2000)
Winkler P.: Isometric embeddings in products of complete graphs. Discret. Appl. Math. 7, 221–225 (1984)
Zaretskii K.A.: Construction of trees using the distances between pendent vertices. Uspekhi Math. Nauk. 20, 90–92 (1965)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ilić, A., Ilić, M. Generalizations of Wiener Polarity Index and Terminal Wiener Index. Graphs and Combinatorics 29, 1403–1416 (2013). https://doi.org/10.1007/s00373-012-1215-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-012-1215-6