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

ПРЕПРИНТ 08/2015

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

This preprint was accepted November 27,  2015

АННОТАЦИЯ:
©
    Пусть  $G$ --- связный граф на $n\ge 2$  вершинах,  в котором длина наибольшей цепочки последовательно соединённых вершин степени 2 не превосходит $k$ а обхват не менее $g$.  Обозначим через $u(G)$ максимальное количество листьев в остовном дереве графа $G$. 
В работе доказано, что $u(G) \ge \alpha_{g,k}(v(G)-k-2) +2$, где $\alpha_{g,1}= {\left[{g+1\over 2}\right] \over 
                 4\left[{g+1\over 2}\right]+1}$ и $\alpha_{g,k}={1\over 2k+2}$ при $k\ge 2$.
 
Приводятся бесконечные серии примеров, показывающих  точность   доказанных оценок.

  
  

D. V. Karpov

LOWER BOUNDS ON THE NUMBER OF LEAVWS IN SPANNING TREES

ABSTRACT:

  Let  $G$ be a connected graph on  $n\ge 2$  vertices of girth at least $g$. 
Let maximal chain of successively adjacent vertices of degree 2 in  the graph $G$ does not exceed $k\ge 1$.
Denote by $u(G)$ the maximal number of leaves in a spanning tree of~$G$.  We prove, that $u(G) \ge \alpha_{g,k}(v(G)-k-2) +2$, where $\alpha_{g,1}= {\left[{g+1\over 2}\right] \over 
                 4\left[{g+1\over 2}\right]+1}$ and $\alpha_{g,k}={1\over 2k+2}$ при $k\ge 2$.
 
We present infinite series of examples showing that all these bounds are tight.