"Записки научных семинаров ПОМИ"
Том 450 , стр. 62-73
Нижние оценки количества листьев в остовных деревьях
Д. В. Карпов
С.-Петербургское отделение Математического института
им. В А. Стеклова РАН, Фонтанка 27,
191023 С.-Петербург;
С.-Петербургский государственный университет,
Университетский пр. 28, Старый Петергоф,
198504, Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Пусть $G$ -- связный граф на $n\ge 2$ вершинах, в котором длина наибольшей цепочки последовательно соединённых вершин степени 2 не превосходит $k$ а обхват не менее $g$. Обозначим через $u(G)$ максимальное количество листьев в остовном дереве графа $G$.
В работе доказано, что $u(G) \ge \alpha_{g,k}(v(G)-k-2) +2$, где $\alpha_{g,1}= {\left[{g+1\over 2}\right] \over
4\left[{g+1\over 2}\right]+1}$ и $\alpha_{g,k}={1\over 2k+2}$ при $k\ge 2$.
Приводятся бесконечные серии примеров, показывающих точность доказанных оценок.
Библ. -- 14 назв.
- Ключевые слова: остовное дерево, количество листьев
[spanning tree, number of leaves]
Полный текст(.pdf)