"Записки научных семинаров ПОМИ"
Том 497, стр. 53-79
Критерий наличия такого цикла, что множество не входящих в него вершин независимо
Н. А. Кароль
РЭШ
kolya.karol.99@mail.ru
- Аннотация:
Наша работа содержит критерий наличия в двусвязном графе такого цикла,
что множество не входящих в него вершин независимо, в
терминах минимальной степени вершин графа. А именно, если в двусвязном графе $n$ вершин,
а минимальная степень вершин графа не менее, чем $\frac{n + 2}{3}$,
то в нём существует такой цикл, что множество не входящих в него вершин независимо.
Библ. -- 4 назв.
- Ключевые слова: независимое множество, двусвязный граф, минимальная степень, длинный цикл
[independent set, biconnected graph, minimum degree]
Полный текст(.pdf)