Previous |  Up |  Next

Article

Keywords:
distance; diameter; Wiener index; reverse Wiener index; trees; starlike trees; caterpillars
Summary:
The reverse Wiener index of a connected graph $G$ is defined as \[ \Lambda (G)=\frac {1}{2}n(n-1)d-W(G), \] where $n$ is the number of vertices, $d$ is the diameter, and $W(G)$ is the Wiener index (the sum of distances between all unordered pairs of vertices) of $G$. We determine the $n$-vertex non-starlike trees with the first four largest reverse Wiener indices for $n\ge 8$, and the $n$-vertex non-starlike non-caterpillar trees with the first four largest reverse Wiener indices for $n\ge 10$.
References:
[1] Althöfer, I.: Average distances in undirected graphs and the removal of vertices. J. Comb. Theory, Ser. B 48 (1990), 140-142. DOI 10.1016/0095-8956(90)90136-N | MR 1047559 | Zbl 0688.05045
[2] Balaban, A. T., Mills, D., Ivanciuc, O., Basak, S. C.: Reverse Wiener indices. Croat. Chem. Acta 73 (2000), 923-941.
[3] Cai, X., Zhou, B.: Reverse Wiener indices of connected graphs. MATCH Commun. Math. Comput. Chem. 60 (2008), 95-105. MR 2423500
[4] Chung, F. R. K.: The average distance and the independence number. J. Graph Theory 12 (1988), 229-235. DOI 10.1002/jgt.3190120213 | MR 0940832 | Zbl 0644.05029
[5] Dankelmann, P., Mukwembi, S., Swart, H. C.: Average distance and vertex-connectivity. J. Graph Theory 62 (2009), 157-177. DOI 10.1002/jgt.20395 | MR 2555095 | Zbl 1221.05108
[6] Dobrynin, A. A., Entringer, R., Gutman, I.: Wiener index of trees: Theory and applications. Acta Appl. Math. 66 (2001), 211-249. DOI 10.1023/A:1010767517079 | MR 1843259 | Zbl 0982.05044
[7] Du, Z., Zhou, B.: A note on Wiener indices of unicyclic graphs. Ars Comb. 93 (2009), 97-103. MR 2566742 | Zbl 1224.05139
[8] Du, Z., Zhou, B.: Minimum on Wiener indices of trees and unicyclic graphs of given matching number. MATCH Commun. Math. Comput. Chem. 63 (2010), 101-112. MR 2582967
[9] Du, Z., Zhou, B.: On the reverse Wiener indices of unicyclic graphs. Acta Appl. Math. 106 (2009), 293-306. DOI 10.1007/s10440-008-9298-z | MR 2497411 | Zbl 1172.05351
[10] Entringer, R. C., Jackson, D. E., Snyder, D. A.: Distance in graphs. Czech. Math. J. 26 (1976), 283-296. MR 0543771 | Zbl 0329.05112
[11] Hosoya, H.: Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull. Chem. Soc. Japan 44 (1971), 2332-2339. DOI 10.1246/bcsj.44.2332
[12] Ivanciuc, O., Ivanciuc, T., Balaban, A. T.: Quantitative structure-property relationship evaluation of structural descriptors derived from the distance and reverse Wiener matrices. Internet Electron. J. Mol. Des. 1 (2002), 467-487.
[13] Luo, W., Zhou, B.: Further properties of reverse Wiener index. MATCH Commun. Math. Comput. Chem. 61 (2009), 653-661. MR 2514237 | Zbl 1224.05149
[14] Luo, W., Zhou, B.: On ordinary and reverse Wiener indices of non-caterpillars. Math. Comput. Modelling 50 (2009), 188-193. DOI 10.1016/j.mcm.2009.02.010 | MR 2542600 | Zbl 1185.05146
[15] Luo, W., Zhou, B., Trinajstić, N., Du, Z.: Reverse Wiener indices of graphs of exactly two cycles. Util. Math., in press.
[16] Nikolić, S., Trinajstić, N., Mihalić, Z.: The Wiener index: Development and applications. Croat. Chem. Acta 68 (1995), 105-128.
[17] Plesník, J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8 (1984), 1-21. DOI 10.1002/jgt.3190080102 | MR 0732013 | Zbl 0552.05048
[18] Rouvray, D. H.: The rich legacy of half a century of the Wiener index. D. H. Rouvray and R. B. King Topology in Chemistry-Discrete Mathematics of Molecules, Norwood, Chichester (2002), 16-37.
[19] Trinajstić, N.: Chemical Graph Theory, 2nd revised edn. CRC press, Boca Raton (1992), 241-245. MR 1169298
[20] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947), 17-20. DOI 10.1021/ja01193a005
[21] Zhang, B., Zhou, B.: On modified and reverse Wiener indices of trees. Z. Naturforsch. 61a (2006), 536-540.
[22] Zhou, B., Trinajstić, N.: Mathematical properties of molecular descriptors based on distances. Croat. Chem. Acta 83 (2010), 227-242.
[23] Zhou, B.: Reverse Wiener index. I. Gutman and B. Furtula Novel Molecular Structure Descriptors-Theory and Applications II, Univ. Kragujevac, Kragujevac (2010), 193-204. Zbl 1194.92092
Partner of
EuDML logo