RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2020, том 497, страницы 53–79 (Mi znsl7027)

Критерий наличия такого цикла, что множество не входящих в него вершин независимо

Н. А. Кароль

РЭШ

Аннотация: Наша работа содержит критерий наличия в двусвязном графе такого цикла, что множество не входящих в него вершин независимо, в терминах минимальной степени вершин графа. А именно, если в двусвязном графе $n$ вершин, а минимальная степень вершин графа не менее, чем $\frac{n + 2}{3}$, то в нём существует такой цикл, что множество не входящих в него вершин независимо. Библ. – 4 назв.

Ключевые слова: независимое множество, двусвязный граф, минимальная степень, длинный цикл.

УДК: 519.17

Поступило: 01.11.2020



© МИАН, 2024