All but 49 Numbers are Wiener Indices of Trees
Tóm tắt
The Wiener index is one of the main descriptors that correlate a chemical compound’s molecular graph with experimentally gathered data regarding the compound’s characteristics. A long standing conjecture on the Wiener index ([4, 5]) states that for any positive integer
$n$
(except numbers from a given 49 element set), one can find a tree with Wiener index
$n$
. In this paper, we prove that every integer
$n>10^8$
is the Wiener index of some short caterpillar tree with at most six non-leaf vertices. The Wiener index conjecture for trees then follows from this and the computational results in [8] and [5].
Tài liệu tham khảo
Dobrynin, A.A., Entringer, R., Gutman, I.: Wiener index of trees: Theory and applications. Acta Appl. Math. 66, 211–249 (2001)
Goldman, D., Istrail, S., Lancia, G., Piccolboni, A.: Algorithmic strategies in combinatorial chemistry. In: Proc. 11th ACM-SIAM Sympos. Discrete Algorithms, pp. 275–284, (2000)
Grosswald, E.: Representations of Integers as Sums of Squares. Springer, Berlin Heidelberg New York (1985)
Gutman, I., Yeh, Y.: The sum of all distances in bipartite graphs. Math. Slovaca 45, 327–334 (1995)
Lepović, M., Gutman, I.: A collective property of trees and chemical trees. J. Chem. Inf. Comput. Sci. 38, 823–826 (1998)
Wiener, H.: Structural determination of paraffin boiling points. J. Amer. Chem. Soc. 69, 17–20 (1947)
Ban, Y.A., Bespamyatnikh, S., Mustafa, N.H.: On a conjecture on Wiener indices in combinatorial chemistry. In: Proc. of the 9th International Computing and Combinatorics Conference ’03, pp. 509–518, 2003. (The journal version will appear in Algorithmica, 2004)