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

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

Предположим, что ${\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).}$

Примеры

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

Свойства

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

Примечания

Ссылки

• Chris Godsil, Brendan McKay, от 7 февраля 2022 на Wayback Machine .