Geodesic
A New Proof of a Result Concerning a Complete Description of $ (n, n + 2) $-Graphs with Maximum Value of the Hosoya Index
Matematičeskie zametki, Tome 111 (2022) no. 2, pp. 258-276

Voir la notice de l'article provenant de la source Math-Net.Ru

The Hosoya index is an important topological index of graphs defined as the number of their matchings. At present, for any $ n $ and $ k \in \{- 1,0,1,2 \}$, all connected graphs with $ n $ vertices and $ n + k $ edges that have a maximum value of the Hosoya index among all such graphs have been described (in the case $ k = 2 $ for $ n \ge 15 $). This paper proposes a new proof for the case $ k = 2 $ for $ n \ge 17$ based on a decomposition of the Hosoya index by subsets of separating vertices and local graph transformations induced by them. This approach is new in the search for graphs with extreme value of the Hosoya index, where many standard techniques are usually employed. The new proof is more combinatorial, shorter, and less technical than the original proof.
Keywords: matching, extremal combinatorics. 
@article{MZM_2022_111_2_a7,
     author = {N. A. Kuz'min and D. S. Malyshev},
     title = {A {New} {Proof} of a {Result} {Concerning} a {Complete} {Description} of $ (n, n + 2) ${-Graphs} with {Maximum} {Value} of the {Hosoya} {Index}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {258--276},
     publisher = {mathdoc},
     volume = {111},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2022_111_2_a7/}
}
TY  - JOUR
AU  - N. A. Kuz'min
AU  - D. S. Malyshev
TI  - A New Proof of a Result Concerning a Complete Description of $ (n, n + 2) $-Graphs with Maximum Value of the Hosoya Index
JO  - Matematičeskie zametki
PY  - 2022
SP  - 258
EP  - 276
VL  - 111
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2022_111_2_a7/
LA  - ru
ID  - MZM_2022_111_2_a7
ER  - 
%0 Journal Article
%A N. A. Kuz'min
%A D. S. Malyshev
%T A New Proof of a Result Concerning a Complete Description of $ (n, n + 2) $-Graphs with Maximum Value of the Hosoya Index
%J Matematičeskie zametki
%D 2022
%P 258-276
%V 111
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2022_111_2_a7/
%G ru
%F MZM_2022_111_2_a7
N. A. Kuz'min; D. S. Malyshev. A New Proof of a Result Concerning a Complete Description of $ (n, n + 2) $-Graphs with Maximum Value of the Hosoya Index. Matematičeskie zametki, Tome 111 (2022) no. 2, pp. 258-276. http://geodesic.mathdoc.fr/item/MZM_2022_111_2_a7/