"Записки научных семинаров ПОМИ"
Том 381, стр. 78-87
Остовные деревья с большим количеством висячих вершин
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27,
191023 Санкт-Петербург, Россия
dvk@pdmi.ras.ru
- Аннотация: Пусть $G$ -- связный граф, в котором максимальная
цепочка последовательно соединённых вершин степени 2
состоит из $k>0$ вершин. В работе доказывается, что
у графа $G$ существует остовное дерево, в котором
более ${1\over 2k+4}$ всех вершин являются висячими.
С помощью серии примеров показывается, что константу~${1\over 2k+4}$
нельзя заменить на большую.
Библ. -- 7 назв.
- Ключевые слова: Остовное дерево, висячие вершины, количество висячих вершин
[spanning tree, leaves, number of leaves]
Полный текст(.pdf)