Гипотеза Брэттона

Материал из WikiGrapp
Перейти к:навигация, поиск

Гипотеза Брэттона (Conjecture of Bratton) — У всякого сильно связного графа без петель с m дугами и n вершинами диаметр больше или равен \delta(m,n)-1, где \delta(m,n) определяется следующим образом. Пусть q — частное, а r — остаток от деления n-1 на \nu = m-n+1. Тогда

\delta(m,n) = \left\{ \begin{array}{l} 2q\mbox{ при } r = 0, \\
2q+1\mbox{ при } r = 1, \\ 2q+2\mbox{ при } r \geq 2.
\end{array} \right.

Гипотеза решена М.Гольдбергом в 1966 г. (См. Докл. АН СССР, Т. 170, N 4, 1966).

Литература

  • Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.