"Записки научных семинаров ПОМИ"
Том 391, стр. 5-17
Оценки количества висячих
вершин в остовных деревьях в графах без треугольников
А. В. Банкевич
С.-Петербургский
государственный университет,
Университетский пр. 28,
Петродворец, 198504 Санкт-Петербург, Россия
anton.bankevich@gmail.com
- Аннотация:В работе доказывается, что у связного графа с обхватом
по крайней мере $4$, в котором $s$ вершин степени, отличной
от 2, существует остовное дерево, в котором
не менее ${1\over 3}(s-2)+2$ висячих вершин.
Приведена серия примеров, показывающая точность оценки.
Этот результат в совокупности с доказанной ранее оценкой
для графов без ограничения на обхват (в таких графах можно
выделить остовное дерево, в котором не менее
${1\over 4}(s-2)+2$ висячих вершин) порождает гипотезу,
что для графа с обхватом по крайней мере $g$ существует
остовное дерево, в котором не менее
$\frac{g - 2}{2g - 2}(s-2)+2$ висячих вершин (в этом случае
приведённая оценка окажется точной). В работе показано,
что эта гипотеза может быть верна только для небольших значений
$g < 10$ и оценка не может быть более сильной, чем $\frac{7}{16}s$.
Библ. -- 14 назв.
- Ключевые слова: остовное дерево, висячие вершины,
количество висячих вершин
[spanning tree, leaves, number of leaves]
Полный текст(.pdf)