On the palindromic Hosoya polynomial of trees

Abstract

A graph $G$ on $n$ vertices of diameter $D$ is called $H$-palindromic if $\alpha (G,k)=\alpha (G,D-k)$ for all $k=0,1,\dots ,\lfloor \frac{D}{2}\rfloor$, where $\alpha (G,k)$ is the number of unordered pairs of vertices at distance $k$. Quantities $\alpha (G,k)$ form coefficients of the Hosoya polynomial. In 1999, Caporossi, Dobrynin, Gutman and Hansen showed that there are exactly five $H$-palindromic trees of even diameter and conjectured that there are no such trees of odd diameter. We prove this conjecture for bipartite graphs. An infinite family of $H$-palindromic trees of diameter $6$ is also constructed.

5 pages, 1 figure, 2 tables