Пятница, 16 ноября, комната 106. Начало в 17:45.
Докладчик: А. Б. Зыкова.
Тема: Построение минимального связного доминирующего множества в графе.
Пусть --- связный граф с минимальной степенью вершины
и
вершинами. В 1981 г. N.Linial высказал гипотезу о том, что в таком графе существует остовное дерево более, чем с
висячими вершинами (то есть связное доминирующее множество не более, чем из
вершин). Для
эта гипотеза была доказана.
Однако, из работы N.Alon ``Transversal numbers of hypergraphs'' следует, что для больших эта оценка неверна: вероятностным методом доказано, что есть графы, в которых минимальное доминирующее множество имеет не менее
вершин.
Доклад будет состоять в построении связного доминирующего множества, содержащего не более, чем вершин, где
--- константа, не зависящая от
и
.