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

ПРЕПРИНТ 02/2011

ОЦЕНКИ КОЛИЧЕСТВА ВИСЯЧИХ ВЕРШИН В ОСТОВНЫХ ДЕРЕВЬЯХ

This preprint was accepted February, 2011

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

Пусть $G$ --- связный граф обхвата не менее $g$, в котором длина наибольшей цепочки последовательно соединённых вершин степени 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
Ключевые слова:остовное дерево,  висячие вершины, количество висячих вершин
 





A.V.Bankevich,     D.V.Karpov     




BOUNDS OF THE NUMBER OF LEAVES IN SPANNING TREES



ABSTRACT:
Let $G$ be a connected graph with $s$ vertices of degree not 2. We prove that  $G$ has a spanning tree  with at least 
${1\over 4}(s-2)+2$ leaves.


Let $G$ be a connected graph with girth at least $g$. Let  maximal chain of vertices of degree 2 in the graph $G$ consists of $k>0$ vertices. We prove that $G$ has a spanning tree  with   at least $\alpha_{g,k}(v(G)-k-2)+2$ leaves, where
$\alpha_{g,k}=   {[{g+1\over2}]\over [{g+1\over2}](k+3)+1}$   for  $k Key words: spanning tree, leaves, number of leaves



[Full text:
Preprint in Russian (.pdf.gz)]


 







Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg