Прикладная теория графов

Явная конструкция бесконечных семейств сильно регулярных орграфов с параметрами $((v+(2^{n+1}-4)t)2^{n-1}, k+(2^n-2)t, t, \lambda, t)$

В. А. Бызов, И. А. Пушкарев

Вятский государственный университет, г. Киров, Россия

Аннотация: Описана явная конструкция бесконечных последовательностей сильно регулярных орграфов с наборами параметров $((v+(2^{n+1}-4)t)2^{n-1}, k+(2^n-2)t, t, \lambda, t)$. Для поиска начальных орграфов использована компьютерная программа, остальные члены последовательности получены с помощью рекуррентного алгоритма. Найдено $11$ семейств сильно регулярных орграфов. В частности, эти семейства содержат орграфы $\text{dsrg}(40, 10, 3, 1, 3)$, $\text{dsrg}(72, 18, 5, 3, 5)$, $\text{dsrg}(76, 19, 5, 4, 5)$, $\text{dsrg}(92, 23, 6, 5, 6)$ и $\text{dsrg}(104, 26, 7, 5, 7)$, вопрос существования которых ранее был открыт.

Ключевые слова: сильно регулярный орграф, рекуррентная последовательность, обменная матрица, произведение Кронекера, Artelys Knitro.

УДК: 519.172.3

DOI: 10.17223/20710410/69/7