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/

[1] H. Hosoya, “Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbon”, Bull. Chem. Soc. Japan, 44 (1971), 2332–2339 | DOI

[2] H. Hosoya, “The topological index $Z$ before and after 1971”, Internet Electron. J. Mol. Des., 1 (2002), 428–442 | DOI

[3] H. Hosoya, “Important mathematical structures of the topological index $Z$ for tree graphs”, J. Chem. Inform. Model., 47 (2007), 744–750 | DOI

[4] H. Hosoya, “Mathematical meaning and importance of the topological index $Z$”, Croatica Chemica Acta, 80 (2007), 239–249

[5] I. Gutman, “Acyclic systems with extremal Hückel $\pi$-electron energy”, Theoret. Chem. Accounts, 45 (1977), 79–87 | DOI

[6] J. Ou, “On extremal unicyclic molecular graphs with maximal Hosoya index”, Discrete Appl. Math., 157 (2009), 391–397 | DOI | Zbl

[7] H. Deng, “The largest Hosoya index of $(n,n+1)$-graphs”, Comput. Math. Appl., 56 (2008), 2499–2506 | DOI | Zbl

[8] Y. Liu, W. Zhuang, Z. Liang, “Largest Hosoya index and smallest Merrifeld–Simmons index in tricyclic graphs”, MATCH Commun. Math. Comput. Chem., 73 (2015), 195–224 | Zbl

[9] A. M. Magomedov, T. A. Magomedov, S. A. Lavrenchenko, “Vzaimno-rekurrentnye formuly dlya perechisleniya razbienii pryamougolnika”, PDM, 2019, no. 46, 108–121 | DOI | Zbl