УДК 519.17
О деревьях радиуса 2 с максимальным количеством паросочетаний
Н. А. Кузьмин1
| Аннотация | Паросочетанием в графе называется любое множество его попарно не смежных ребер. В настоящей статье рассматривается и решается задача максимизации количества паросочетаний в деревьях радиуса не более чем 2 с заданным количеством вершин. Было выявлено, что для любого $n\ge 56$, где $n=3k+r$, $k\in{\mathbb N},r\in \{0,1,2\}$, экстремальное дерево единственно; оно получается соединением вершины с центральными вершинами в $b$ копиях 3-пути и с листовыми вершинами в $a$ копиях 2-пути, где $b = k+\dfrac{r - 1 - 2a}{3}$, $(r,a)\in \{(0,1),(1,0),(2,2)\}$. Для любого $6\le n\le 55$ соответствующее экстремальное дерево тоже единственно (кроме $n=8$, когда имеется два таких дерева) и устроено подобным образом, при $1\le n\le 5$ единственным экстремальным деревом является путь на $n$ вершинах. Для доказательства этих фактов были предложены некоторые преобразования графов, увеличивающие количество паросочетаний и сохраняющие число вершин. Автор надеется, что данные преобразования будут полезны для решения аналогичных задач в других классах графов. |
|---|---|
| Ключевые слова | экстремальная теория графов, паросочетание, дерево, максимальное дерево, молекулярные графы, обыкновенные графы |
1Кузьмин Никита Александрович, студент, ФГАОУ ВО «Национальный исследовательский университет «Высшая школа экономики» (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12), ORCID: https://orcid.org/0000-0002-8478-3502, nikita.kuz2000@gmail.com
Цитирование: Кузьмин Н. А. О деревьях радиуса 2 с максимальным количеством паросочетаний // Журнал Средневолжского математического общества. 2020. Т. 22, № 2. С. 177–187.
DOI 10.15507/2079-6900.22.202002.177-187
