Laboratory of Mathematical Logic at PDMI

Пятница, 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$.