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

ПРЕПРИНТ 15/2011

ОСТОВНЫЕ ДЕРЕВЬЯ С БОЛЬШИМ КОЛИЧЕСТВОМ ВИСЯЧИХ ВЕРШИН: НОВЫЕ ОЦЕНКИ ЧЕРЕЗ КОЛИЧЕСТВО ВЕРШИН СТЕПЕНЕЙ 3 И НЕ МЕНЕЕ 4

This preprint was accepted November 23, 2011

АННОТАЦИЯ:
 В работе доказывается, что  у  связного графа $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$. Тем самым, доказана точность 
всех оценок.

D. V. Karpov

SPANNING TREES WITH MANY LEAVES: NEW LOWER BOUNDS IN TERMS OF NUMBER OF VERTICES OF DEGREE 3 AND AT LEAST 4

ABSTRACT:
We prove, that every connected graph with $s$ vertices of degree 3 and $t$ vertices of degree at least 4
has a spanning tree  with   at least ${2\over 5}t +{1\over 5}s+\alpha$  leaves, where $\alpha \ge {8\over 5}$.
Moreover, $\alpha \ge 2$ for all graphs besides three graphs-exclusions. All exclusion are  regular graphs of degree 4, they are explicitly described in the paper. 


We present infinite series of graphs, containing only vertices of degrees 3 and 4, for which the maximal number of leaves in a spanning tree is equal for ${2\over 5}t +{1\over 5}s+2$. Therefore we prove that our bound
is tight.