Прогулочно-регулярный граф

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Прогулка-обычный график»  -  новости  · газеты  · книги  · ученый  · JSTOR ( октябрь 2019 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Эта статья, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Октябрь 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Предположим, что это простой граф. Пусть обозначим матрицу смежности из , обозначим множество вершин , и обозначим характеристический полином вершинно- удален подграфа для всех Тогда следующие условия эквивалентны:${\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] [ ненадежный источник ]}
• На заочных регулярных графах являются ходить регулярно. В более общем смысле любой простой граф в однородной когерентной алгебре блуждающе-регулярен.
• Связный регулярный граф является регулярным, если: ^{[ сомнительно - обсудить ] [ необходима ссылка ]}
  • Он имеет не более четырех различных собственных значений.
  • Он не содержит треугольников и имеет не более пяти различных собственных значений.
  • Он двудольный и имеет не более шести различных собственных значений.

Свойства [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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