MSC2020 05C35
On radius 2 trees with the maximum number of matchings
N. A. Kuzmin1
| Annotation | 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 |
1Nikita A. Kuzmin, student, National Research University Higher School of Economics (25/12 Bolshaya Pecherskaya St., Nizhny Novgorod 603155, Russia), ORCID: https://orcid.org/0000-0002-8478-3502, nikita.kuz2000@gmail.com
Citation: N. A. Kuzmin, "[On radius 2 trees with the maximum number of matchings]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,22:2 (2020) 177–187 (In Russian)
DOI 10.15507/2079-6900.22.202002.177-187
