Граф регулярных блужданий

Граф регулярных блужданий — простой граф, в котором число замкнутых блужданий любой длины от вершины в неё же не зависит от выбора вершины.

Предположим, что ${\displaystyle G}$ является простым графом. Пусть ${\displaystyle A}$ означает матрицу смежности графа ${\displaystyle G}$, ${\displaystyle V(G)}$ означает множество вершин графа ${\displaystyle G}$, а ${\displaystyle \Phi _{G-v}(x)}$ означает характеристический многочлен подграфа ${\displaystyle G-v}$ с удалённой вершиной ${\displaystyle v\in V(G).}$ Следующие утверждения эквивалентны:

• ${\displaystyle G}$ является графом регулярных блужданий.
• ${\displaystyle A^{k}}$ является диагональной матрицей с константой по диагонали для всех ${\displaystyle k\geqslant 0.}$
• ${\displaystyle \Phi _{G-u}(x)=\Phi _{G-v}(x)}$ для всех ${\displaystyle u,v\in V(G).}$

• Вершинно-транзитивные графы являются графами регулярных блужданий.
• Полусимметричные графы являются графами регулярных блужданий.
• Дистанционно-регулярные графы являются графами регулярных блужданий.
• Связный регулярный граф является графом регулярных блужданий, если^[1].
  • Он имеет не более четырёх различных собственных значений.
  • Он свободен от треугольников и имеет не более пяти различных собственных значений.
  • Он двудольный и имеет не более шести различных собственных значений.

• Граф регулярных блужданий является обязательно регулярным.
• Дополнение графа регулярных блужданий является графом регулярных блужданий.
• Прямое произведение графов регулярных блужданий является графом регулярных блужданий.
• Тензорное произведение графов регулярных блужданий является графом регулярных блужданий.
• Сильное произведение графов регулярных блужданий является графом регулярных блужданий.
• В общем случае рёберный граф регулярных блужданий не является графом регулярных блужданий.

• Chris Godsil, Brendan McKay, Feasibility conditions for the existence of walk-regular graphs Архивная копия от 7 февраля 2022 на Wayback Machine.