Almost All Trees and Chemical Trees Have Equiseparable Mates



1 Introduction

A tree is a connected acyclic graph. A chemical tree is a tree in which no vertex has degree greater than 4. Chemical trees represent acyclic organic molecules (alkanes and similar) and belong among the most studied objects of chemical graph theory [1].
Let T be an n-vertex tree and e = (xy) its edge. By n1(e|T) and n2(e|T) we denote the number of vertices of T, lying on the two sides of the edge e. Then, of course, n1(e|T) + n2(e|T) = n.
More formally, n1(e|T) and n2(e|T) are the number of vertices of T, lying closer to vertex x than to vertex y, and closer to vertex y than to vertex x, respectively. Still more formally, n1(e|T) and n2(e|T) are the cardinalities of the sets { u Î V(T) ; d(u,x)<d(v,x) } and { u ÎV(T) ; d(u,x)>d(v,x) }, respectively, where V(T) is the vertex set of T and where d(r,s) stands for the distance between the vertices r and s.
In what follows the numbers n1(e|T) and n2(e|T) will be chosen so that n1(e|T) <= n2(e|T). This convention does not influence the generality of our considerations. Then, in the case of an n-vertex tree T, the value of n1(e|T) cannot be greater than n/2 (i. e., n/2 if n is even, and (n - 1)/2 if n is odd).
The quantities n1(e|T) and n2(e|T) were encountered already in the 1947 paper by Harold Wiener [2], where he showed that the sum of distances between all pairs of vertices of a chemical tree:

can be computed by means of the formula

Nowadays W is called the Wiener index.
The first formal proof of Eq. (1) was given in the book [3]. Eventually, Eq. (1) was much studied; for details see the review [4]. The extension of the right-hand side of (1) to all graphs was named the Szeged index; for details see the review [5] and the book [1].
Motivated by Eq. (1), in 2001 the modified Wiener index, was defined as [6]

Somewhat more recently, also the variable Wiener index was put forward [7, 8], viz.:

with l being an adjustable parameter. For l = +1 and l = -1, the variable Wiener index reduces, respectively, to the ordinary and to the modified Wiener index.
A further structure-descriptor U, proposed by Zen-kevich [9], can be expressed in terms of the numbers n1(e|T) and n2(e|T) as [10]:

where C 12.0 and H 1.0 are the relative atomic masses of carbon and hydrogen, respectively.
In Eqs. (1)-(4) the summation goes over all edges of the tree T.
Studies of the above mentioned structure-descriptors lead to the concept of equiseparable trees [11]. Two trees T' and T" of equal number n of vertices are said to be equiseparable if their edges e1',e2',...,en-1' and e1",e2",...,en-1" can be labelled so that the equality n1(ei'|T') = n1(ei"|T") holds for all i = 1,2,...,n - 1. From the inspection of Eqs. (1)-(4) we see that equiseparable trees have equal Wiener indices, Wl-values (for all l), as well as equal Zenkevich indices U.
It is known [12] that the Wiener index measures the van der Waals surface area of an alkane molecule, which explains the correlations found between W and a great variety of physico-chemical properties of alkanes (for details see the reviews [13, 14]). The Zenkevich index provides a measure of the internal (vibrational) energy of the underlying alkane molecule [10, 15]. Unfortunately, if two or more chemical trees are equiseparable, then the mentioned physico-chemical properties of the respective compounds cannot be distinguished by means of the Wiener-type structure-descriptors. Thus, equiseparability represents a serious drawback of the Wiener-type structure-descriptors. We now show that only a negligibly small fraction of all trees and all chemical trees is not suffering from equiseparability. The vast majority of trees and chemical trees have numerous equiseparable mates. This implies that the chemical applicability of the above specified molecular structure-descriptors is limited much more than previously anticipated, and calls for caution when practical applications thereof are undertaken.
General procedures for constructing pairs of equiseparable trees were developed [11, 16], and it gradually became evident [17] that equiseparable trees and chemical trees occur in large families. In order to gain information on the frequency of the occurrence of equiseparable trees, we examined all trees with up to 20 vertices [17]. We found that with increasing n, the number of n-vertex trees and chemical trees having noequiseparable mate becomes negligibly small relative to the total number of trees and chemical trees; the respective data are given in Table 1. In Table 1, T(n) and CT(n) denote the number of distinct n-vertex trees and chemical trees, respectively. Among them only A(n) trees and only CA(n) chemical trees have no equiseparable mates.

Table 1. The numbers T(n) and CT(n) of distinct n-vertex trees and chemical trees, respectively, and the numbers A(n) and CA(n) of such trees having no equiseparable mates.

The results shown in Table 1 suggest that with increasing n the ratios A(n)/T(n) and CA(n)/CT(n) tend to zero. This, in turn, would imply that almost all trees and almost all chemical trees have an equiseparable mate. In what follows we demonstrate that this, indeed, is the case.
We first need some preparations.

2 The Separation Sequence

Let T be an n-vertex tree and e1,e2,...,en-1 its edges. Let ki(T) among the numbers n1(ei|T) , i = 1,2,...,n - 1, be equal to i. Then the ordered ( n/2 )-tuple

is independent of the labelling of the edges of T. We refer to s(T) as to the separation equence of T. Clearly, two trees are equiseparable if and only if their separation sequances coincide.
Since an n-vertex tree has n - 1 edges, we have

Thus the separation sequence is an ( n/2 )-tuple of integers (either positive or zero) whose sum is equal to n - 1. Of course, not all ( n/2 )-tuples of such integers pertain to trees.

3 The Main Result and Its Proof

Theorem 1. Almost all trees have an equiseparable mate,i. e.,

Theorem 2. Almost all chemical trees have anequiseparable mate, i. e.,

Proof of Theorem 1. For the sake of simplicity we assume that n is even, i. e., that n/2 = n/2. The consideration of the case of odd n is fully analogous.
According to a standard result of Combinatorics (see, e. g. [18]), the number of ordered p-tuples of non-negative integers whose sum is equal to q is equal to . Consequently, the number of (n/2)-tuples of integers (either positive or zero) whose sum is equal to n - 1 is equal to . Therefore,

By the well known Cayley's formula, the number of labelled n-vertex trees is equal to nn-2. Because the vertices of an n-vertex graph can be labelled in at most n! distinct ways,

Define an auxiliary function

In view of (9) and (10), if the condition

holds, then the limit (7) will also be satisfied, implying the validity of Theorem 1.
Bearing in mind that we arrive at

Applying the Stirling formula [18] n! ~ (n/e)n we obtain that for large values of n,

The relation

holds because Therefore also (11) holds. Therefore also (7) holds.
Theorem 2 follows from a somewhat stronger result. Let T(n,D) be the number of trees in which the greatest vertex degree is equal to D. Let B(n,D) be the number of such trees having an equiseparable mate among trees with greatest vertex degree D. Using a reasoning analogous to, but somewhat more complicated than, the proof of Theorem 1, we can demonstrate the validity of:
Theorem 3. For D >= 3, almost all trees whose greatest vertex degree is D have an equiseparable mate among trees whose greatest vertex degree is D, i. e.,

Details of the proof of Theorem 3 are omitted. Theorem 2 is a special case of Theorem 3 for D = 3 and D = 4.


[ 1] M. V. Diudea, I. Gutman, L. Jantchi, Molecular Topology, Nova, New York (2002).
[ 2] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc, 69, 17–20 (1947).
[ 3] I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer–Verlag, Berlin (1986).
[ 4] A. A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211–249 (2001).
[ 5] I. Gutman, A. A. Dobrynin, The Szeged index – a success story, Graph Theory Notes New York, 34, 37–44 (1998).
[ 6] S. Nikolic, N. Trinajstic, M. Randic, Wiener index revisited, Chem. Phys. Lett., 333, 319–321 (2001).
[ 7] I. Gutman, D. Vukicevic, J. Zerovnik, A class of modified Wiener indices, Croat. Chem. Acta, 77, 103–109 (2004).
[ 8] B. Lucic, A. Milicevic, S. Nikolic, N. Trinajstic, On variable Wiener index, Indian J. Chem., 42A, 1279–1282 (2003).
[ 9] I. G. Zenkevich, Dependence of chromatographic retention indices on the dynamic characteristics of molecules, Russ. J. Phys. Chem., 73, 797–801 (1999).
[10] I. Gutman, I. G. Zenkevich, Wiener index and vibrational energy, Z. Naturforsch, 57a, 824–828 (2002).
[11] I. Gutman, B. Arsic, B. Furtula, Equiseparable chemical trees, J. Serb. Chem. Soc., 68, 549–555 (2003).
[12] I. Gutman, T. Kortvelyesi, Wiener indices and molecular surfaces, Z. Naturforsch., 50a, 669–671 (1995).
[13] I. Gutman, Y. N. Yeh, S. L. Lee, Y. L. Luo, Some recent results in the theory of the Wiener number, Indian J. Chem., 32A, 651–661 (1993).
[14] D. H. Rouvray, The rich legacy of half century of the Wiener index, Topology in Chemistry – Discrete Mathematics of Molecules, ed. by D. H. Rouvray, R. B. King, Horwood, Chichester (2002), pp. 16–37.
[15] I. Gutman, D. Vidovic, B. Furtula, I. G. Zenkevich, Wiener–type indices and internal molecular energy, J. Serb. Chem. Soc., 68, 401–408 (2003).
[16] I. Gutman, B. Furtula, D. Vukicevic, B. Arsic, Equiseparable molecules and molecular graphs, Indian J. Chem., 43A, 7–10 (2004).
[17] O. Miljkovic, B. Furtula, I. Gutman, Statistics of equiseparable trees and chemical trees, MATCH Commun. Math. Comput. Chem., 51, 179–184 (2004).
[18] I. Tomescu, Introduction to Combinatorics, Collet's, London (1975).