|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Новое доказательство результата о полном описании $(n,n+2)$-графов c максимальным значением индекса Хосойи
Н. А. Кузьминab, Д. С. Малышевab a Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде
b Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского
Аннотация:
Индекс Хосойи – это важный топологический индекс графов, определяемый как
количество их паросочетаний. На настоящее время для любых $n$ и $k\in\{-1,0,1,2\}$
полностью описаны все связные графы с $n$ вершинами и $n+k$ ребрами,
имеющие максимальное значение индекса Хосойи среди всех таких графов
(в случае $k=2$ при $n\ge 15$). В данной работе предлагается новое
доказательство для случая $k=2$ при $n\ge 17$, основанное на разложении
индекса Хосойи по подмножествам отделяющих вершин и порождаемых ими
локальных заменах графов. Данный подход является новым для тематики поиска
графов с экстремальным значением индекса Хосойи, где обычно используется
ряд стандартных приемов. Новое доказательство более комбинаторное и короткое
и менее техническое, чем оригинальное.
Библиография: 9 названий.
Ключевые слова:
паросочетание, экстремальная комбинаторика.
Поступило: 05.05.2021 Исправленный вариант: 16.08.2021
Образец цитирования:
Н. А. Кузьмин, Д. С. Малышев, “Новое доказательство результата о полном описании $(n,n+2)$-графов c максимальным значением индекса Хосойи”, Матем. заметки, 111:2 (2022), 258–276; Math. Notes, 111:2 (2022), 258–272
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm13139https://doi.org/10.4213/mzm13139 https://www.mathnet.ru/rus/mzm/v111/i2/p258
|
Статистика просмотров: |
Страница аннотации: | 282 | PDF полного текста: | 40 | Список литературы: | 56 | Первая страница: | 17 |
|