Прогулочно-регулярный граф - Walk-regular graph - Wikipedia

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

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

Предположим, что ${\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\geq 0.}$
• ${\displaystyle \Phi _{G-u}(x)=\Phi _{G-v}(x)}$ для всех ${\displaystyle u,v\in V(G).}$

Примеры

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

Характеристики

• Блуждающий регулярный граф обязательно является правильным графом.
• Дополнения блуждающих регулярных графов блуждающе-регулярны.
• Декартовы произведения блуждающих регулярных графов блуждающие регулярны.
• Категориальные продукты блуждающих регулярных графов блуждающе-регулярны.
• Сильные продукты блуждающих регулярных графов блуждающе-регулярны.
• В целом линейный график блуждающего регулярного графа не является блуждающим.

Рекомендации

1. «Есть ли только конечное число различных кубических графов, которые не являются ни вершинно-транзитивными, ни дистанционно регулярными?». mathoverflow.net. Получено 2017-07-21.

внешняя ссылка

• Крис Годсил и Брендан МакКей, Условия допустимости существования блуждающих графов.