О числе некритических вершин в сильно связных орграфах

По определению, вершина $w$ сильно связного (или, просто, сильного) орграфа $D$ является некритической, если подорграф $D-w$ также сильно связен. Доказано, что если минимальная полустепень $k$ исхода (захода) вершин $D$ больше или равна двум, то в нем найдутся, по крайней мере, $k$ некритических вершин. В отличие от неориентированного случая эта оценка не может быть улучшена для фиксированного $k$ даже при большом порядке орграфа. Кроме того, показано, что если степень любой вершины сильного направленного графа порядка $n$ больше или равна $3/4n$, то он содержит, по крайней мере, две некритические вершины. Соответствующее доказательство использует результаты теории максимальных собственных сильных подорграфов, основанной Мадером и в дальнейшем развитой автором. Аналог этой теории построен также для двусвязных (неориентированных) графов.
Библиография: 11 названий.