Ходьба-регулярный граф

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

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

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

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

Примеры

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

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

Граф, регулярный по обходу, обязательно является регулярным графом.
Дополнения к графам, регулярным по ходьбе, являются регулярными по ходьбе.
Декартовы произведения графов, регулярных по ходьбе, являются регулярными по ходьбе.
Категориальные произведения графов, регулярных по ходьбе, являются регулярными по ходьбе.
Сильные произведения графов, регулярных по ходьбе, являются регулярными по ходьбе.
В общем случае линейный график регулярного по шагам графа не является регулярным по шагам.

k-walk-регулярные графы

График $k$ -ходить регулярно, если для любых двух вершин $v$ и $w$ расстояния максимум $k,$ количество прогулок по длине $l$ от $v$ к $w$ зависит только от $k$ и $l$ . ^[2]

Для $k=0$ это в точности регулярные графы.

Если $k$ не меньше диаметра графа, то $k$ -регулярные графы совпадают с дистанционно регулярными графами .Фактически, если $k\geq 2$ и граф имеет собственное значение кратности не более $k$ (кроме собственных значений $d$ и $-d$ , где $d$ — степень графа), то граф уже дистанционно регулярен. ^[3]

Ссылки

^ «Существует ли лишь конечное число различных кубических регулярных графов, которые не являются ни вершинно-транзитивными, ни дистанционно регулярными?» . mathoverflow.net . Проверено 21 июля 2017 г.
^ Кристина Дальфо, Мигель Анхель Фиол и Эрнест Гаррига, «На $k$ -Регулярные графы ходьбы», Электронный журнал комбинаторики 16 (1) (2009), статья R47.
^ Марк Камара и др., «Геометрические аспекты регулярных графов с двумя обходами», Линейная алгебра и ее приложения 439 (9) (2013), 2692-2710.

Внешние ссылки

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

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

[2] Кристина Дальфо, Мигель Анхель Фиол и Эрнест Гаррига, «На $k$ -Регулярные графы ходьбы», Электронный журнал комбинаторики 16 (1) (2009), статья R47.

[3] Марк Камара и др., «Геометрические аспекты регулярных графов с двумя обходами», Линейная алгебра и ее приложения 439 (9) (2013), 2692-2710.

[1]

[2]

[3]