2021/12/21 by Dmitry Badulin, Badulin, Dmitry, Alexandr Grebennikov +3
Chemistry · Mathematics · #05C09 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Synthesis and Properties of Aromatic Compounds
paper · pdf · doi:10.48550/arxiv.2112.11164
openalex publication_date 2021/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G on n vertices of diameter D is called H-palindromic if α(G,k) = α(G,D-k) for all k=0, 1, …, \lfloor(D)/(2) \rfloor, where α(G,k) is the number of unordered pairs of vertices at distance k. Quantities α(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.