Home

Семинар 14 сентября 2001 года

Пятница, 14 сентября, комната 106. Начало в 17:00.

Докладчик: Д. В. Карпов.

СВЯЗЬ КОЛИЧЕСТВА ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ КУБИЧЕСКОГО ГРАФА И КОЛИЧЕСТВА ПОДГРАФОВ K_4^-.
Рассматривается связный граф~$ G $, степени вершин которого не менее трех. Доказывается, что ограничение на долю вершин степени три, входящих в подграфы $ K_4^- $, позволяет гарантировать большее количество висячих вершин в остовном дереве такого графа. Все оценки снизу на количество висячих вершин доказываются с помощью полиномиальных алгоритмов.