On the Palindromic Hosoya Polynomial of Trees

Standard

On the Palindromic Hosoya Polynomial of Trees. / Badulin, Dmitry; Grebennikov, Alexandr; Vorob'ev, Konstantin.

In: Match, Vol. 88, No. 2, 2022, p. 471-478.

Research output: Contribution to journal › Article › peer-review

Author

Badulin, Dmitry ; Grebennikov, Alexandr ; Vorob'ev, Konstantin. / On the Palindromic Hosoya Polynomial of Trees. In: Match. 2022 ; Vol. 88, No. 2. pp. 471-478.

BibTeX

@article{dd94fe30e2dd4f64ad264f18c79eb064,

title = "On the Palindromic Hosoya Polynomial of Trees",

abstract = "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.",

author = "Dmitry Badulin and Alexandr Grebennikov and Konstantin Vorob'ev",

year = "2022",

doi = "10.46793/match.88-2.471B",

language = "English",

volume = "88",

pages = "471--478",

journal = "Match",

issn = "0340-6253",

publisher = "University of Kragujevac",

number = "2",

}

RIS

TY - JOUR

T1 - On the Palindromic Hosoya Polynomial of Trees

AU - Badulin, Dmitry

AU - Grebennikov, Alexandr

AU - Vorob'ev, Konstantin

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85129639318&partnerID=8YFLogxK

U2 - 10.46793/match.88-2.471B

DO - 10.46793/match.88-2.471B

M3 - Article

AN - SCOPUS:85129639318

VL - 88

SP - 471

EP - 478

JO - Match

JF - Match

SN - 0340-6253

IS - 2

ER -

ID: 98340648