On 5- and 6-Leaved Trees

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

Matematičeskie zametki, Tome 115 (2024) no. 3, pp. 371-384

Résumé

A matching of a graph is a set of its edges that pairwise do not have common vertices. An important parameter of graphs, which is used in mathematical chemistry, is the Hosoya index, defined as the number of their matchings. Previously, the problems of maximizing this index were considered and completely solved for $n$-vertex trees with two, three and four leaves, for any sufficiently large $n$. In the present paper, a similar problem is completely solved for 5-leaved trees with $n\geqslant 20$ and for 6-leaved trees with $n\geqslant 26$.

Détail

Keywords: extremal combinatorics, $z$-index, tree, leaf.

Bibliographie

[1] H. Wiener, “Structural determination of paraffin boiling points”, J. Amer. Chem. Soc., 1:69 (1947), 17–20 | DOI

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

[3] H. Hosoya, “The topological index $Z$ before and after 1971”, Int. Elect. J. Molecular Design, 34:15 (2003), 428–442

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

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

[6] H. Hosoya, “The most private features of the topological index”, MATI, 1 (2019), 25–33

[7] I. Gutman, “Acyclic systems with extremal Hückel $\pi$-electron energy”, Theor. Chim. Acta, 45 (1977), 79–87 | DOI

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

[9] J. Ou, “On acyclic molecular graphs with maximal Hosoya index, energy, and short diameter”, J. Math. Chem., 43:1 (2008), 221–233 | MR

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

[11] B. Sahin, “On Hosoya index and Merrifield-Simmons index of trees with given domination number”, Numer. Methods Partial Differential Equations, 38:4 (2020), 904–915 | DOI | MR

[12] S. Wagner, “Extremal trees with respect to Hosoya index and Merrifield–Simmons index”, MATCH Commun. Math. Comput. Chem., 57:1 (2007), 221–233 | MR

[13] L. Xu, “The second largest Hosoya index of unicyclic graphs”, MATCH Commun. Math. Comput. Chem., 62:3 (2007), 621–628 | MR

[14] K. Xu, “The Hosoya indices and Merrifield–Simmons indices of graphs with connectivity at most $k$”, Appl. Math. Lett., 25:3 (2012), 476–480 | DOI | MR

[15] K. Xu, I. Gutman, “The greatest Hosoya index of bicyclic graphs with given maximum degree”, MATCH Commun. Math. Comput. Chem., 66:3 (2011), 795–824 | MR

[16] W. Yan, L. Ye, “On the maximal energy and the Hosoya index of a type of trees with many pendant vertices”, MATCH Commun. Math. Comput. Chem., 53:2 (2005), 449–459 | MR

[17] N. A. Kuzmin, “O derevyakh radiusa 2 s maksimalnym kolichestvom parosochetanii”, Zhurnal SVMO, 22:2 (2020), 177–187 | DOI

[18] N. A. Kuzmin, D. C. Malyshev, “Novoe dokazatelstvo rezultata o polnom opisanii $(n,n+2)$-grafov c maksimalnym znacheniem indeksa Khosoii”, Matem. zametki, 111:2 (2022), 258–276 | DOI | MR

[19] N. A. Kuzmin, D. C. Malyshev, “O derevyakh diametra 5 s maksimalnym kolichestvom parosochetanii”, Matem. sb., 214:2 (2023), 143–154 | DOI | MR