Граф регулярных блужданий — простой граф, в котором число замкнутых блужданий любой длины от вершины в неё же не зависит от выбора вершины.
Эквивалентные определения Предположим, что является простым графом. Пусть означает матрицу смежности графа , означает множество вершин графа , а означает характеристический многочлен подграфа с удалённой вершиной Следующие утверждения эквивалентны: является графом регулярных блужданий. является диагональной матрицей с константой по диагонали для всех для всех
Примеры Вершинно-транзитивные графы являются графами регулярных блужданий. Полусимметричные графы являются графами регулярных блужданий. Дистанционно-регулярные графы являются графами регулярных блужданий. Связный регулярный граф является графом регулярных блужданий, если: Он имеет не более четырёх различных собственных значений. Он свободен от треугольников и имеет не более пяти различных собственных значений. Он двудольный и имеет не более шести различных собственных значений.
Свойства Граф регулярных блужданий является обязательно регулярным. Дополнение графа регулярных блужданий является графом регулярных блужданий. Прямое произведение графов регулярных блужданий является графом регулярных блужданий. Тензорное произведение графов регулярных блужданий является графом регулярных блужданий. Сильное произведение графов регулярных блужданий является графом регулярных блужданий. В общем случае рёберный граф регулярных блужданий не является графом регулярных блужданий.
Примечания
Ссылки Chris Godsil, Brendan McKay, Feasibility conditions for the existence of walk-regular graphs .
Категория:Алгебраическая теория графов Категория:Регулярные графы Категория:Семейства графов