О разности между максимальной степенью и индексом графа

Аннотация

Рассматривается алгебраический параметр графа – разность между его максимальной степенью и спектральным радиусом. Хорошо известно, что этот графовый параметр является всегда неотрицательным и представляет собой некоторую меру отклонения графа от регулярности. В последние два десятилетия множество статей было посвящено изучению этого параметра. В частности, в 2007 г. американским математиком S. M. Cioabă получена его нижняя оценка, зависящая от порядка и диаметра графа. В 2017 г. при изучении верхней и нижней оценок для этого параметра M. R. Oboudi выдвинул гипотезу о том, что нижней оценкой данного параметра для произвольного графа является разность между максимальной степенью и спектральным радиусом цепи. Это очень похоже на аналогичное утверждение для спектрального радиуса произвольного графа, нижней границей которого тоже является спектральный радиус цепи. Здесь вышеуказанная гипотеза подтверждается для некоторых классов графов.