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

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

Эквивалентные определения

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

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

Примеры

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

Свойства

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

Ссылки

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