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

Том 406, стр. 31-66

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

dvk0@yandex.ru

Аннотация: В работе доказывается, что у связного графа $G$, в котором $s$ вершин степени 3 и $t$ вершин степени не менее 4, существует остовное дерево, в котором ${2\over 5}t +{1\over 5}s+\alpha$ висячих вершин, где $\alpha \ge {8\over 5}$. Доказано, что для всех графов, кроме трёх исключений, $\alpha \ge 2$. Исключение составляют единственный регулярный граф степени 4 на 6 вершинах и два регулярных графа степени 4 на 8 вершинах (в которых каждое ребро входит в треугольник). Приводится бесконечная серия примеров графов, содержащих только вершины степеней 3 и 4, для которых максимальное количество висячих вершин в остовном дереве равно ${2\over 5}t +{1\over 5}s+2$. Тем самым, доказана точность всех оценок. Библ. -- 12 назв.
Ключевые слова:остовное дерево, висячие вершины, количество висячих вершин [spanning tree, leaves, number of leaves]