О двудольных \(Q\)-полиномиальных графах диаметра, не большего 5

Биткина В. В. , Махнев А. А.
Владикавказский математический журнал. 2025. Том 27. Выпуск 3.С.21-27.

Аннотация:
Пусть \(u\) - вершина двудольного \(Q\)-полиномиального дистанционно регулярного графа \(\Gamma\) диаметра \(D\ge 3\), \(\Sigma=\Gamma_D(u)\) и \(\Lambda=\Sigma_2\). Тогда \(\Lambda\) - дистанционно регулярный \(Q\)-полиномиальный граф. В случаях \(D=4\) и \(D=5\) граф \(\Lambda\) является сильно регулярным \(Q\)-полиномиальным. Половинный граф \(\Gamma_2\) сильно регулярен и \(\Lambda\) - окрестность вершины в дополнении к \(\Gamma_2\). Поэтому необходимое условие \(Q\)-полиномиальности \(\Gamma\) - это сильная регулярность окрестностей и антиокрестностей вершин в \(\Lambda\).
Двудольный дистанционно регулярный граф \(\Gamma\) диаметра \(D\in \{4,5\}\) назовем почти \(Q\)-полиномиальным, если окрестности и  антиокрестности вершин в дополнении его половинного графа сильно регулярны. Имеется два допустимых массива пересечений \(Q\)-полиномиальных графов: \(\{10,9,8,7,6;1,2,3,4,10\}\) (свернутый 10-куб) и \(\{55,54,50,35,10;1,5,20,45,55\}\). Эти графы имеют сильно регулярные графы \(\Lambda\) (параметры \((126,25,8,4)\) и \((210,99,48,45)\)) и окрестности вершин в \(\Lambda\) (параметры \((25,8,4,2)\) и \((99,48,22,24)\)). Имеются два допустимых массива пересечений, отвечающих графам на \(704\) вершинах: \(\{26,25,24,2,1;1,2,24,25,26\}\) и \(\{36,34,32,4,1;1,4,32,34,36\}\). В работе изучаются почти \mbox{\(Q\)-полиномиальные} графы диаметра \(5\). Доказано, что дистанционно регулярные графы с массивами пересечений \(\{26,25,24,2,1;1,2,24,25,26\}\) и \(\{36,35,32,4,1;1,4,32,35,36\}\) не существуют.

Ключевые слова: дистанционно регулярный граф, \(Q\)-полиномиальный граф, двудольный граф

+ Список литературы