RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2023 Volume 214, Number 2, Pages 143–154 (Mi sm9745)

This article is cited in 1 paper

On diameter $5$ trees with the maximum number of matchings

N. A. Kuz'min, D. S. Malyshev

National Research University Higher School of Economics, Nizhnii Novgorod, Russia

Abstract: A matching in a graph is any set of edges of this graph without common vertices. The number of matchings, also known as the Hosoya index of the graph, is an important parameter, which finds wide applications in mathematical chemistry. Previously, the problem of maximizing the Hosoya index in trees of radius $2$ (that is, diameter $4$) of fixed size was completely solved. This work considers the problem of maximizing the Hosoya index in trees of diameter $5$ on a fixed number $n$ of vertices and solves it completely. It turns out that for any $n$ the extremal tree is unique.
Bibliography: 6 titles.

Keywords: extremal graph theory, matching, tree.

MSC: 05C09

Received: 05.03.2022

DOI: 10.4213/sm9745


 English version:
Sbornik: Mathematics, 2023, 214:2, 273–284

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024