Home

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

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

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

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

Abstract

Пусть $ G $ --- связный граф с минимальной степенью вершины $ d>=3 $ и $ n $ вершинами. В 1981 г. N.Linial высказал гипотезу о том, что в таком графе существует остовное дерево более, чем с $ n(d-2)/(d+1) $ висячими вершинами (то есть связное доминирующее множество не более, чем из $ 3n/(d+1) $ вершин). Для $ n=3,4,5 $ эта гипотеза была доказана.

Однако, из работы N.Alon ``Transversal numbers of hypergraphs'' следует, что для больших $ d $ эта оценка неверна: вероятностным методом доказано, что есть графы, в которых минимальное доминирующее множество имеет не менее $ n(ln(d+1)+o(1))/(d+1) $ вершин.

Доклад будет состоять в построении связного доминирующего множества, содержащего не более, чем $ n(ln(d+1)+c)/(d+1) $ вершин, где $ c $ --- константа, не зависящая от $ n $ и $ d $.