Geodesic
On radius 2 trees with the maximum number of matchings
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 2, pp. 177-187.

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

A matching in a graph is any set of its pairwise non-adjacent edges. In this paper, we consider and solve the maximization problem of the matchings number in radius $\le2$ trees of a given number of vertices. For any $n\ge 56$, where $n=3k+r$ and $k\in{\mathbb N},r\in \{0,1,2\}$, an extremal tree is unique and it is a join of a vertex with the central vertices in $b$ copies of $P_3$ and with leaf vertices in $a$ copies of $P_2$, where $b = k+\dfrac{r - 1 - 2a}{3}$ and $(r,a)\in \{(0,1),(1,0),(2,2)\}$. For any $6\le n\le 55$, a corresponding extremal tree is also unique (except $n=8$, where there are two such trees) and it has a similar structure. For any $1\le n\le 5$, a unique extremal tree is the path on $n$ vertices. To prove these facts, we propose some graph transformations, increasing the matchings number and keeping the vertices number. The author hopes that these transformations will be useful for solving similar problems in other classes of graphs.
Keywords: extremal graph theory, matching, tree, maximum tree, molecular graphs, ordinary graphs. 
@article{SVMO_2020_22_2_a3,
     author = {N. A. Kuzmin},
     title = {On radius 2 trees with the maximum number of matchings},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {177--187},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2020_22_2_a3/}
}
TY  - JOUR
AU  - N. A. Kuzmin
TI  - On radius 2 trees with the maximum number of matchings
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2020
SP  - 177
EP  - 187
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2020_22_2_a3/
LA  - ru
ID  - SVMO_2020_22_2_a3
ER  - 
%0 Journal Article
%A N. A. Kuzmin
%T On radius 2 trees with the maximum number of matchings
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2020
%P 177-187
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2020_22_2_a3/
%G ru
%F SVMO_2020_22_2_a3
N. A. Kuzmin. On radius 2 trees with the maximum number of matchings. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 2, pp. 177-187. http://geodesic.mathdoc.fr/item/SVMO_2020_22_2_a3/

[1] J. Moon, L. Moser, “On cliques in graphs”, Israel Journal of Mathematics, 3:1 (1965), 23–28 (In English) | DOI | MR | Zbl

[2] J. Liu, “Maximal independent sets in bipartite graphs”, Journal of Graph Theory, 17:1 (1993), 495–507 (In English) | DOI | MR | Zbl

[3] M. Hujter, Z. Tuza, “The number of maximal independent sets in triangle-free graphs”, SIAM Journal of Discrete Mathematics, 6:2 (1993), 284–288 (In English) | DOI | MR | Zbl

[4] M. J. Jou, G. Chang, “The number of maximum independent sets in graphs”, Taiwanese Journal of Mathematics, 4:4 (2000), 685–695 (In English) | DOI | MR | Zbl

[5] B. E. Sagan, “A note on independent sets in trees”, SIAM Journal of Discrete Mathematics, 1:1 (1988), 105–108 (In English) | DOI | MR | Zbl

[6] C. Heuberger, S. Wagner, “Maximizing the number of independent subsets over trees with bounded degree”, Journal of Graph Theory, 58:1 (2008), 49–68 (In English) | DOI | MR | Zbl

[7] D. S. Taletskii, D. S. Malyshev, “On trees of bounded degree with maximal number of greatest independent sets”, Diskretnyy analiz i issledovaniye operatsiy, 25:2 (2018), 101–123 | MR | Zbl

[8] D. S. Taletskii, D. S. Malyshev, “Trees without duplicated leaves with a minimum number of greatest independent sets”, Diskretnaya matematika, 30:4 (2018), 115–133 | DOI | MR

[9] I. Gutman, “Acyclic systems with extremal Huckel $\pi$-electron energy”, Theoretical Chemistry Accounts, 45:2 (1977), 79–87 (In English) | DOI

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

[11] J. Ou, “Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching”, Applied Mathematics Letters, 19:7 (2006), 652–656 (In English) | DOI | MR | Zbl

[12] H. Deng, “The largest Hosoya index of $(n, n+1)$-graphs”, Computers and Mathematics with Applications, 56:10 (2008), 2499–2506 (In English) | DOI | MR | Zbl

[13] C. Heuberger, S. Wagner, “The number of maximum matchings in a tree”, Discrete Mathematics, 311:21 (2011), 2512–2542 (In English) | DOI | MR | Zbl