"Записки научных семинаров ПОМИ"
Том 406, стр. 67-94
Остовные деревья с большим количеством висячих вершин:
нижние оценки через количество вершин степеней 1, 3 и не менее 4
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН
Фонтанка 27, 191023 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
В работе доказывается, что у связного графа $G$, в котором $t$ вершин
степени не менее 4 и $s$ вершин степеней 1 и 3, существует остовное дерево, в котором не менее
${1\over 3}t +{1\over 4}s+{3\over 2}$ висячих вершин.
Приводится бесконечная серия примеров графов, доказывающая точность оценки.
Библ. -- 13 назв.
- Ключевые слова:остовное дерево, висячие вершины, количество висячих вершин
[spanning tree, leaves, number of leaves]
Полный текст(.pdf)