Пятница, 25 марта, 106. Начало в 18:00.
Докладчик: С.А. Образцова.
Тема: О вершинах степени
минимальных и минимальных относительно стягивания
-связных графов: верхние оценки..
Abstract
В статье
Р. Халина был задан вопрос о том, какова наибольшая константа
![$ c_k $](../../../sites/default/files/tex/a8739cfa2350fd446c3306d108092c669b732d91/index.png)
,
такая, что количество вершин
степени
![$ k $](../../../sites/default/files/tex/79e444938ea5a2ffa8be21e3720171935e8fbb42/index.png)
в минимальном и минимальном по стягиванию
![$ k $](../../../sites/default/files/tex/79e444938ea5a2ffa8be21e3720171935e8fbb42/index.png)
-связном
графе
![$ G $](../../../sites/default/files/tex/0c55de2f440a0837e81f13a2c0aa07d023ec1565/index.png)
равно по крайней мере
![$ c_k|G| $](../../../sites/default/files/tex/6ccf664996213960a3ebea078e45ec3f4ba62abe/index.png)
. На настоящий момент для
![$ k=4 $](../../../sites/default/files/tex/dc8d2c9a990bff2c9f1ef64e72769e52f0a36ee3/index.png)
известна точная оценка (а именно
![$ c_4=1 $](../../../sites/default/files/tex/e438fdc8511965034a97ef1992106e8802eb4188/index.png)
) и для
![$ k \geq 5 $](../../../sites/default/files/tex/02f850af8d75ea65a4470a0a314fa3dbad128b01/index.png)
неизвестно никаких верхних оценок. В докладе будут построены серии
графов, с помощью которых доказываются верхние оценки для
![$ c_k $](../../../sites/default/files/tex/a8739cfa2350fd446c3306d108092c669b732d91/index.png)
при
всех
![$ k \geq 5 $](../../../sites/default/files/tex/02f850af8d75ea65a4470a0a314fa3dbad128b01/index.png)
.