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/