Оценки экспонентов примитивных графов | Прикладная дискретная математика. 2011. № 2(12).

Уточнены оценки экспонентов для n-вершинных примитивных орграфов (неотрицательных матриц порядка n), содержащих два простых контура, длины которых взаимно просты. Получены достижимые оценки порядка O(max{lA,/(l,X,n)}), где l и А - взаимно простые длины простых контуров в орграфе и /(l,A, n) - линейный полином. Описан полностью класс примитивных орграфов, на которых достигается абсолютная оценка экспонента n2 - 2n + 2 (H. Wielandt, 1950).Для экспонентов неориентированных n-вершинных примитивных графов доказаны уточняющие оценки. В частности, если l - длина длиннейшего простого цикла нечетной длины в графе Г, то экспонент графа Г не превышает 2n - l - 1. Описан полностью класс примитивных неориентированных графов, на которых достигается абсолютная оценка экспонента 2n - 2.