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

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

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

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

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (7 февраля 2022) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (7 февраля 2022) Статья содержит ошибки и/или опечатки. Проверить статью на грамматические, орфографические и пунктуационные ошибки. Необходимо проверить её на соответствие грамматическим, орфографическим или пунктуационным нормам русского языка. (7 февраля 2022) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.