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

ПРЕПРИНТ 16/2011

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

This preprint was accepted November 24, 2011

АННОТАЦИЯ:
 В работе доказывается, что  у  связного графа $G$, в котором $t$ вершин 
степени не менее 4 и $s$ вершин степеней 1 и 3,  существует остовное дерево, в котором  не менее 
${1\over 3}t +{1\over 4}s+{3\over 2}$ висячих вершин.
Приводится бесконечная серия примеров графов, доказывающая точность всех оценок.
всех оценок.

D. V. Karpov

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

ABSTRACT:
We prove, that every connected graph with $s$ vertices of degree~1 and~3 and~$t$ vertices of degree at least~4
has a spanning tree  with   at least ${1\over 3}t +{1\over 4}s+{3\over 2}$  leaves.
We present infinite series of graphs,  for which this bound is tight.