Almost All Trees and Chemical Trees Have Equiseparable Mates

Damir VUKICEVICa* and Ivan GUTMANb

aDepartment of Mathematics, University of Split
bFaculty of Science
P. O. Box 60, 34000 Kragujevac, Serbia & Montenegro

(Received: March 15, 2004; Accepted for publication: July 6, 2004; Published on Web: August 6, 2004)

Let T be an n-vertex tree and e its edge. By n1(e|T) and n2(e|T) are denoted the number of vertices of T lying on the two sides of e; n1(e|T) + n2(e|T) = n. Conventionally, n1(e|T) <= n2(e|T). If T' and T" are two trees with the same number n of vertices, and if their edges e1',e2',...,en-1' and e1",e2",...,en-1" can be labelled so that n1(ei'|T') = n1(ei"|T") holds for all i=1,2,...,n-1, then T' and T" are said to be equiseparable. Several previously studied molecular-graph-based structure-descriptors have equal values for equiseparable trees, which is a disadvantageous property of these descriptors. In earlier works large families of equiseparable trees have been found. We now show that equiseparability is ubiquitous, and that almost all trees have an equiseparable mate. The same is true for chemical trees.

Keywords: Equiseparability, Wiener index, Chemical tree

Abstract in Japanese

Text in English

PDF file(63kB)