Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zhurnal SVMO:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva, 2020, Volume 22, Number 2, Pages 177–187
DOI: https://doi.org/10.15507/2079-6900.22.202002.177-187
(Mi svmo767)
 

This article is cited in 2 scientific papers (total in 2 papers)

Mathematics

On radius 2 trees with the maximum number of matchings

N. A. Kuzmin

National Research University – Higher School of Economics in Nizhny Novgorod
Full-text PDF (309 kB) Citations (2)
References:
Abstract: 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.
Document Type: Article
UDC: 519.17
MSC: 05C35
Language: Russian
Citation: N. A. Kuzmin, “On radius 2 trees with the maximum number of matchings”, Zhurnal SVMO, 22:2 (2020), 177–187
Citation in format AMSBIB
\Bibitem{Kuz20}
\by N.~A.~Kuzmin
\paper On radius 2 trees with the maximum number of matchings
\jour Zhurnal SVMO
\yr 2020
\vol 22
\issue 2
\pages 177--187
\mathnet{http://mi.mathnet.ru/svmo767}
\crossref{https://doi.org/10.15507/2079-6900.22.202002.177-187}
Linking options:
  • https://www.mathnet.ru/eng/svmo767
  • https://www.mathnet.ru/eng/svmo/v22/i2/p177
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva
    Statistics & downloads:
    Abstract page:222
    Full-text PDF :117
    References:37
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024