Вестник российских университетов. Математика,
2025, том 30, выпуск 150,страницы 110–127(Mi vtamu351)
Научные статьи
Proof of Brouwer's Conjecture (BC) for all graphs with number of vertices $n>n_0$ assuming that BC holds for $n\leq n_0$ for some $n_0 \leq 10^{24}$
[Доказательство гипотезы Брауэра (ГБ) для всех графов с числом вершин $n>n_0$ в предположении, что ГБ выполняется при $n\leq n_0$ для некоторого $n_0 \leq 10^{24}$]
Аннотация:
В работе рассматривается проблема построения верхней оценки для суммы максимальных собственных чисел лапласиана графа. Статья посвящена доказательству гипотезы Брауэра, которая состоит в том, что сумма $t$-максимальных собственных чисел лапласиана графа не превышает числа ребер графа плюс $(t+1)t/2$. Отметим, что мы доказываем справедливость общей гипотезы Брауэра в предположении справедливости гипотезы для конечного числа графов с числом вершин меньше $10^{24}$, т.е. полное доказательство гипотезы сводится к установлению ее справедливости для конечного числа графов. Доказательство данной гипотезы привлекает интерес большого числа специалистов. Имеется ряд результатов для специальных графов и доказательство справедливости гипотезы для почти всех случайных графов. Рассматриваемое нами доказательство использует индуктивный метод, имеющий ряд особенностей. Оригинальный метод предполагает построение различных оценок для собственных чисел лапласиана, который используется для построения шага индукции. Рассматриваются несколько вариантов метода в зависимости от величин координат собственных векторов лапласиана. Используется известный факт эквивалентности справедливости гипотезы Брауэра для самого графа и дополнения графа.
Ключевые слова:
лапласиан графа, собственные значения
Полный текст:
PDF файл (601 kB)