Matematicheskie Zametki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Zametki: Year: Volume: Issue: Page: Find

 Mat. Zametki, Forthcoming paper (Mi mz13139)

A new proof of a result about a complete description of $(n,n+2)$-graphs with the maximum value of the Hosoya index

N. A. Kuz'minab, D. S. Malyshevab

a National Research University – Higher School of Economics in Nizhny Novgorod
b National Research Lobachevsky State University of Nizhny Novgorod

Abstract: The Hosoya index is an important topological index of graphs, defined as the number of their matchings. Currently, for any n and k\in{-1,0,1,2}, all connected graphs with n vertices and n+k edges that have the maximum value of the Hosoya index among all such graphs have been described (in the case k = 2 for n>14). This paper proposes a new proof for the case k = 2 for n>16, based on a decomposition of the Hosoya index by subsets of separating vertices and local graph transformations induced by it. This approach is new for the topic of revealing graphs with extremal values of the Hosoya index, where a number of standard techniques are usually used.The new proof is more combinatorial and short and less technical than the original.

Keywords: matching, extremal combinatorics

 Funding Agency Grant Number Russian Science Foundation 21-11-00194

References: PDF file   HTML file
UDC: 519.17