DOI

A graph G on n vertices of diameter D is called H-palindromic if d(G, k) = d(G,D - k) for all k = 0, 1, . . . , [D 2 ] , where d(G, k) is the number of unordered pairs of vertices at distance k. Quantities d(G, k) form coefficients of the Hosoya polynomial. In 1999, Caporossi, Dobrynin, Gutman and Hansen found 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.

Original languageEnglish
Pages (from-to)471-478
Number of pages8
JournalMatch
Volume88
Issue number2
DOIs
StatePublished - 2022

    Scopus subject areas

  • Chemistry(all)
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics

ID: 98340648