Аннотация:
Пусть $G$ – простой граф на $n$ вершинах с весами $\pm 1$ на ребрах. Предположим, что для каждого ребра $e$ сумма весов ребер, смежных с $e$ (включая само $e$), положительна. Пусть $g(n)$ – минимальная возможная сумма весов ребер в $G$. Известно, что $g(n)=(\kappa+o(1)) n^2$. Мы улучшаем нижнюю оценку на $\kappa$ с $-1/25$ до $-1/36$.
Библиография: 5 названий.
Полный текст:
PDF файл (622 kB)
Первая страница:
PDF файл