A survey of recent extremal results on the Wiener index of trees

DOI10.46793/MATCH.92-2.253LMaRDI QIDQ6562215zbMATH OpenFDO

Publication date 26 June 2024

Published in MATCH - Communications in Mathematical and in Computer Chemistry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.46793/MATCH.92-2.253L

graph molecular graph tree Wiener index Wiener index of tree

Trees (05C05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Extremal problems in graph theory (05C35) Chemical graph theory (05C92) Research exposition (monographs, survey articles) pertaining to biology (92-02) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Review text

We don't even know how much of this world is subject to geometry. For instance, structure (or pattern, composition, texture) is one of manifestations of geometry. This review is an example of this: it is a survey of recent extremal results on the Wiener index of trees.\N\NLet all graphs considered in this work are simple and connected (the difference between graph and tree in that the latter has no cycles). The Wiener index of a graph is the sum of the distances between all pairs of vertices. It actually is one of the oldest graph-based structure descriptors, or topological indices, introduced by \textit{H. Wiener} [``Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69, 17--20 (1947)] in 1947 to predict the boiling points of paraffines.\N\NSpeaking generally, chemists are often interested in the Wiener index since it is one of the most classical and well-known topological indices in the molecular graph. It has been extensively studied by chemists and mathematicians over the past years (see for instance [\textit{E. Çela} et al., Discrete Optim. 8, No. 3, 411--416 (2011; Zbl 1233.90282)]).\N\NSince the degrees of a molecular graph correspond to the valences of the atoms, it is one of the most interesting aspects to consider all trees with a prescribed degree sequence. \textit{H. Wang} [Discrete Appl. Math. 156, No. 14, 2647--2654 (2008; Zbl 1155.05020)] and \textit{X.-D. Zhang} and \textit{Q.-Y. Xiang} [MATCH Commun. Math. Comput. Chem. 60, No. 2, 623--644 (2008; Zbl 1195.05022)] independently proved the extremal tree that minimizes the Wiener index is greedy tree through different approaches. Moreover, the extremal tree that maximizes the Wiener index in this category in [Wang, loc. cit.] is incorrect by pointed out in [\textit{H. Wang}, Discrete Appl. Math. 157, No. 18, 3754 (2009; Zbl 1261.05021)] and [\textit{X.-D. Zhang} et al., MATCH Commun. Math. Comput. Chem. 64, No. 3, 661--682 (2010; Zbl 1265.05213)]. Hence, it is still open problem.\N\NThe present review focuses on the extremal results on the Wiener index of trees appeared from 2014 to the present moment. Note that in 2001, Dobrynin, Entringer and Gutman [\textit{A. A. Dobrynin} et al., Acta Appl. Math. 66, No. 3, 211--249 (2001; Zbl 0982.05044)] summarized a great deal of knowledge (both mathematical and chemical) on the Wiener index of trees, including many extremal results. The other extremal results on the Wiener index of trees from 2002 to 2013 were collected in the survey by \textit{K. Xu} et al. [MATCH Commun. Math. Comput. Chem. 71, No. 3, 461--508 (2014; Zbl 1464.05140)]. This survey is restricted to the above defined Wiener index avoiding to examine the related distance-based indices such as hyper-Wiener index, Harary index, Wiener polarity index, and the others. For convenience of discussion, the author of this survey introduces the following notations: the degree of a vertex, a segment, branch, and centroid of a tree. The survey ends with mentioning of the study in 2018 of \textit{J. I. Brown} et al. [Discrete Math. 341, No. 9, 2398--2408 (2018; Zbl 1392.05057)] of the roots of the Wiener polynomials of graphs. Later, in 2020, \textit{D. Wang} [Discrete Math. 343, No. 1, Article ID 111643, 9 p. (2020; Zbl 1429.05105)] proved the theorem that states: Among all trees on \(n > 31\) vertices, the tree \(T_n\) uniquely attains the maximum modulus among all the roots of its Wiener polynomial.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: A survey of recent extremal results on the Wiener index of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6562215)