Groupe d’études et de recherche en analyse des décisions


Trees with Palindromic Hosoya Polynomials

, , et

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.

, 12 pages