Research output: Contribution to journal › Article › peer-review
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 language | English |
---|---|
Pages (from-to) | 471-478 |
Number of pages | 8 |
Journal | Match |
Volume | 88 |
Issue number | 2 |
DOIs | |
State | Published - 2022 |
ID: 98340648