Семинар 16 ноября 2007 года

Пятница, 16 ноября, комната 106. Начало в 17:45.

Докладчик: А. Б. Зыкова.

Тема: Построение минимального связного доминирующего множества в графе.

Abstract

Пусть

--- связный граф с минимальной степенью вершины

и

вершинами. В 1981 г. N.Linial высказал гипотезу о том, что в таком графе существует остовное дерево более, чем с

висячими вершинами (то есть связное доминирующее множество не более, чем из

вершин). Для

эта гипотеза была доказана.

Однако, из работы N.Alon ``Transversal numbers of hypergraphs'' следует, что для больших

эта оценка неверна: вероятностным методом доказано, что есть графы, в которых минимальное доминирующее множество имеет не менее

вершин.

Доклад будет состоять в построении связного доминирующего множества, содержащего не более, чем

вершин, где

--- константа, не зависящая от

и

.