×

Wiener index of graphs with radius two. (English) Zbl 1264.05043

Summary: The Wiener index of a graph is the sum of the distances between all pairs of vertices. It has been one of main descriptors that correlate a chemical compound’s molecular graph with experimentally gathered data regarding the compound’s characteristics. We characterize graphs with the maximum Wiener index among all graphs of order \(n\) with radius two. In addition, we pose a conjecture concerning the minimum Wiener index of graphs with given radius. If this conjecture is true, it will be able to answer an open question by Z. You and B. Liu [MATCH Commun. Math. Comput. Chem. 66, No. 1, 343–344 (2011; Zbl 1264.05040)].

MSC:

05C12 Distance in graphs
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)

Citations:

Zbl 1264.05040
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. A. Dobrynin, R. Entringer, and I. Gutman, “Wiener index of trees: theory and applications,” Acta Applicandae Mathematicae, vol. 66, no. 3, pp. 211-249, 2001. · Zbl 0982.05044 · doi:10.1023/A:1010767517079
[2] M. Aouchiche and P. Hansen, “Automated results and conjectures on average distance in graphs,” in Graph Theory in Paris, Trends in Mathematics, pp. 21-36, Birkhäuser, Basel, Switzerland, 2007. · Zbl 1114.05050 · doi:10.1007/978-3-7643-7400-6_3
[3] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Redwood City, Calif, USA, 1990. · Zbl 0688.05017
[4] A. Chen and F. Zhang, “Wiener index and perfect matchings in random phenylene chains,” MATCH, vol. 61, no. 3, pp. 623-630, 2009. · Zbl 1199.05082
[5] D. Li, B. Wu, X. Yang, and X. An, “Nordhaus-Gaddum-type theorem for Wiener index of graphs when decomposing into three parts,” Discrete Applied Mathematics, vol. 159, no. 15, pp. 1594-1600, 2011. · Zbl 1228.05138 · doi:10.1016/j.dam.2011.06.016
[6] S. G. Wagner, “A class of trees and its Wiener index,” Acta Applicandae Mathematicae, vol. 92, pp. 15-20, 2006.
[7] S. Wagner, “On the Wiener index of random trees,” Discrete Mathematics, vol. 312, no. 9, pp. 1502-1511, 2012. · Zbl 1239.05057 · doi:10.1016/j.disc.2011.05.008
[8] B. Wu, “Wiener index of line graphs,” MATCH, vol. 64, no. 3, pp. 699-706, 2010. · Zbl 1265.05522
[9] S. Yamaguchi, “A note on Wiener index,” MATCH, vol. 60, no. 2, pp. 645-648, 2008. · Zbl 1199.05100
[10] Z. You and B. Liu, “Note on the minimal Wiener index of connected graphs with n vertices and radius r,” MATCH, vol. 66, no. 1, pp. 343-344, 2011. · Zbl 1264.05040
[11] L. Zhang and B. Wu, “The Nordhaus-Goddum-type inequalities for some chemical indices,” MATCH, vol. 54, no. 1, pp. 189-194, 2005. · Zbl 1084.05072
[12] X.-D. Zhang, Q.-Y. Xiang, L.-Q. Xu, and R.-Y. Pan, “The Wiener index of trees with given degree sequences,” MATCH, vol. 60, no. 2, pp. 623-644, 2008. · Zbl 1195.05022
[13] J. Plesník, “On the sum of all distances in a graph or digraph,” Journal of Graph Theory, vol. 8, no. 1, pp. 1-21, 1984. · Zbl 0552.05048 · doi:10.1002/jgt.3190080102
[14] E. DeLaViña and B. Waller, “Spanning trees with many leaves and average distance,” Electronic Journal of Combinatorics, vol. 15, no. 1, article R33, p. 16, 2008. · Zbl 1181.05052
[15] P. Erd\Hos, M. Sakes, and V. T. Sós, “Maximum indueced trees in graphs,” Journal of Combinatorial Theory, Series B, vol. 41, no. 1, pp. 61-79, 1986. · Zbl 0603.05023 · doi:10.1016/0095-8956(86)90028-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.