"Записки научных семинаров ПОМИ"

Том 391, стр. 18-34

С.-Петербургский государственный университет, Университетский пр. 28, Петродворец, 198504 Санкт-Петербург, Россия

anton.bankevich@gmail.com

С.-Петербургское отделение Математического института им. В.А.Стеклова РАН, Фонтанка 27, 191023 Санкт-Петербург, Россия

dvk0@yandex.ru

Аннотация:В работе доказывается, что у связного графа, в котором $s$ вершин степени, отличной от 2, существует остовное дерево, в котором не менее ${1\over 4}(s-2)+2$ висячих вершин. Пусть $G$ -- связный граф обхвата $g$ на $v$ вершинах, в котором длина наибольшей цепочки последовательно соединённых вершин степени 2 не превосходит $k\ge 1$. Доказывается, что у графа $G$ существует остовное дерево, в котором не менее $\alpha_{g,k}(v(G)-k-2)+2$ висячиx вершин, где $\alpha_{g,k}= {[{g+1\over2}]\over [{g+1\over2}](k+3)+1}$ при $k < g-2$ и $\alpha_{g,k}= {g-2\over (g-1)(k+2)}$ при $k\ge g-2$. Библ. -- 12 назв.
Ключевые слова: остовное дерево, висячие вершины, количество висячих вершин [spanning tree, leaves, number of leaves]