### G-99-10

# Trees with Palindromic Hosoya Polynomials

## Gilles Caporossi, AA Dobrynin, Ivan Gutman, and Pierre Hansen

Let *G* be a connected graph and let *D* be its diameter. Denote by *d*(*G,k*) the number of pairs of vertices in *G* that are at distance *k* apart. Assume *d*(*G*,0) is equal to the number of vertices of *G*. Then is the Hosoya polynomial of *G*. [*H*(*G*) was previously referred to as the Wiener polynomial.] In two earlier papers it has been conjectured that if *T* is a tree, then *H*(*T*) cannot be palindromic, i.e., the relations *d*(*T,k*)=*d*(*T,D-k*) cannot be obeyed for all *k*=0,1,...,*D*. We show that the conjecture is not true: the smallest counterexample is a tree with 21 vertices. Yet, up to 26 vertices there exist only five such trees. A number of properties of trees with palindromic Hosoya polynomials are established. We now conjecture that the diameters of all such trees are even.

Published **January 1999**
,
12 pages