"Записки научных семинаров ПОМИ"
Том 406, стр. 107-116
Существование некритических вершин в ориентированных графах
Г. В. Ненашев
С.-Петербургский
государственный университет,
Университетский пр. 28,
Петродворец, 198504 Санкт-Петербург, Россия
glebnen@mail.ru
- Аннотация:
В работе рассматриваются сильно связные орграфы на $n\ge 4$
вершинах. Некритическая вершина сильно связного орграфа --- это вершина,
при удалении которой сохраняется сильная связность. В работе доказано, что
если в таком орграфе сумма степеней любых двух смежных вершин не меньше
$n+1$, то существует некритическая вершина, а если сумма степеней любых
двух смежных вершин не меньше $n+2$, то существуют две некритические
вершины. Примерами показана точность этих оценок. Библ. -- 4 назв.
- Ключевые слова:орграф, сильная связность, некритическая вершина
[digraph, strong connectivity, noncritical vertex]
Полный текст(.pdf)