УДК 519.17
О деревьях радиуса 2 с максимальным количеством паросочетаний
Н. А. Кузьмин1
| Аннотация | Паросочетанием в графе называется любое множество его попарно не смежных ребер. В настоящей статье рассматривается и решается задача максимизации количества паросочетаний в деревьях радиуса не более чем 2 с заданным количеством вершин. Было выявлено, что для любого n≥56, где n=3k+r, k∈N,r∈{0,1,2}, экстремальное дерево единственно; оно получается соединением вершины с центральными вершинами в b копиях 3-пути и с листовыми вершинами в a копиях 2-пути, где b=k+r−1−2a3, (r,a)∈{(0,1),(1,0),(2,2)}. Для любого 6≤n≤55 соответствующее экстремальное дерево тоже единственно (кроме n=8, когда имеется два таких дерева) и устроено подобным образом, при 1≤n≤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
