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

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

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

Предположим, что является простым графом. Пусть означает матрицу смежности графа , означает множество вершин графа , а означает характеристический многочлен подграфа с удалённой вершиной Следующие утверждения эквивалентны:

  • является графом регулярных блужданий.
  • является диагональной матрицей с константой по диагонали для всех
  • для всех

Примеры

Свойства


Примечания

  1. Farrell, Mark . Дата обращения: 21 июля 2017.

Ссылки

Источник —

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