On the palindromic Hosoya polynomial of trees

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, \left \lfloor{\frac{D}{2}}\right \rfloor\), where \(\alpha(G,k)\) is the number of unordered pairs of vertices at distance \(k\). Quantities \(\alpha(G,k)\) form...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-12
Main Authors: Badulin, Dmitry, Grebennikov, Alexandr, Vorob'ev, Konstantin
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Polynomials
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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, \left \lfloor{\frac{D}{2}}\right \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.
ISSN:2331-8422