Пятница, 21 января, ауд. 106. Начало в 18:00.
Докладчик: А.В. Банкевич и Д.В. Карпов.
Тема: Оценки количества висячих вершин в остовных деревьях.
Abstract
Будет доказано, что у связного графа
![$ G $](../../../sites/default/files/tex/0c55de2f440a0837e81f13a2c0aa07d023ec1565/index.png)
, в котором
![$ s $](../../../sites/default/files/tex/c0934f2201bf56f33edc825b3a2d7b7939a7dd0e/index.png)
вершин
степени не равной 2,
существует остовное дерево с не менее чем
![$ {s+6\over 4} $](../../../sites/default/files/tex/b0a1d8efe02699b70823ec77fdceb6ef3d7a32e4/index.png)
висячими вершинами.
Пусть
![$ G $](../../../sites/default/files/tex/0c55de2f440a0837e81f13a2c0aa07d023ec1565/index.png)
--- связный граф обхвата
![$ g $](../../../sites/default/files/tex/7c5d55e3abc26365f64db1b220fd6b1df78da41e/index.png)
, в котором длина наибольшей цепочки
последовательно соединённых вершин степени 2 не превосходит
![$ k\ge 1 $](../../../sites/default/files/tex/7da1e657e1265e59ee6b9be2df71d7d32d51d16e/index.png)
.
Мы докажем, что у графа
![$ G $](../../../sites/default/files/tex/0c55de2f440a0837e81f13a2c0aa07d023ec1565/index.png)
существует остовное дерево, в котором не менее
![$ \alpha_{g,k}(v(G)-k-2)+2 $](../../../sites/default/files/tex/c358d9521faca5e24f0ee98e0fc181673a7208c1/index.png)
висячиx вершин, где
![$ \alpha_{g,k}=
{n\over n(k+3)+1} $](../../../sites/default/files/tex/5708c677967fb3ded3c20b993704b79e9765602b/index.png)
при
![$ k<g-2 $](../../../sites/default/files/tex/09e946ae90261ee0e14e2fb95d78ca67f93c657e/index.png)
(где
![$ n= [{g+1\over2}] $](../../../sites/default/files/tex/bc05b2a288546e02ae7bf27c6c63b6fa8440d35d/index.png)
) и
![$ \alpha_{g,k}= {g-2\over (g-1)(k+2)} $](../../../sites/default/files/tex/749f03ce7458fcf89d0df2a96eb6f405b53911b3/index.png)
при
![$ k\ge g-2 $](../../../sites/default/files/tex/c283d10361d5c8128f653e0c5a7e96aa97d0dbe1/index.png)
.
Будут приведены бесконечные серии примеров, показывающие точность всех
доказанных оценок.