Interested Article - Граф регулярных блужданий
belle
- 2020-09-07
- 1
Граф регулярных блужданий — простой граф , в котором число замкнутых блужданий любой длины от вершины в неё же не зависит от выбора вершины.
Эквивалентные определения
Предположим, что является простым графом. Пусть означает матрицу смежности графа , означает множество вершин графа , а означает характеристический многочлен подграфа с удалённой вершиной Следующие утверждения эквивалентны:
- является графом регулярных блужданий.
- является диагональной матрицей с константой по диагонали для всех
- для всех
Примеры
- Вершинно-транзитивные графы являются графами регулярных блужданий.
- Полусимметричные графы являются графами регулярных блужданий.
- Дистанционно-регулярные графы являются графами регулярных блужданий.
-
Связный
регулярный граф
является графом регулярных блужданий, если
.
- Он имеет не более четырёх различных собственных значений.
- Он свободен от треугольников и имеет не более пяти различных собственных значений.
- Он двудольный и имеет не более шести различных собственных значений.
Свойства
- Граф регулярных блужданий является обязательно регулярным.
- Дополнение графа регулярных блужданий является графом регулярных блужданий.
- Прямое произведение графов регулярных блужданий является графом регулярных блужданий.
- Тензорное произведение графов регулярных блужданий является графом регулярных блужданий.
- Сильное произведение графов регулярных блужданий является графом регулярных блужданий.
- В общем случае рёберный граф регулярных блужданий не является графом регулярных блужданий.
Примечания
- Farrell, Mark . Дата обращения: 21 июля 2017.
Ссылки
- Chris Godsil, Brendan McKay, от 7 февраля 2022 на Wayback Machine .
belle
- 2020-09-07
- 1