Пятница, 14 сентября, комната 106. Начало в 17:00.
Докладчик: Д. В. Карпов.
СВЯЗЬ КОЛИЧЕСТВА ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ КУБИЧЕСКОГО ГРАФА И КОЛИЧЕСТВА ПОДГРАФОВ K_4^-.
Рассматривается связный граф~
![$ G $](../../../sites/default/files/tex/0c55de2f440a0837e81f13a2c0aa07d023ec1565/index.png)
, степени вершин которого не менее трех. Доказывается, что ограничение на долю вершин степени три, входящих в подграфы
![$ K_4^- $](../../../sites/default/files/tex/44ab90550fcd6794cabd43049997ad581e5aaebc/index.png)
, позволяет гарантировать большее количество висячих вершин в остовном дереве такого графа. Все оценки снизу на количество висячих вершин доказываются с помощью полиномиальных алгоритмов.