Бирегулярный граф

Семейства графов, определенные своими автоморфизмами
дистанционно-транзитивный	→	дистанционно-регулярный	←	сильно регулярный
↓
симметричный (дугопереходный)	←	t -транзитивен, t ≥ 2		кососимметричный
↓
(если подключен) вершинно- и реберно-транзитивен	→	реберно-транзитивный и регулярный	→	краево-транзитивный
↓		↓		↓
вершинно-транзитивный	→	обычный	→	(если двусторонний) бирегулярный
↑
Граф Кэли	←	нуль-симметричный		асимметричный

В математике теории графов граф бирегулярный или полурегулярный двудольный граф это двудольный граф $G=(U,V,E)$ для которого каждые две вершины на одной и той же стороне данного двуразделения имеют одинаковую степень друг друга. Если степени вершин в $U$ является $x$ и степень вершин в $V$ является $y$, то говорят, что граф $(x,y)$-бирегулярный.

График ромбододекаэдра бирегулярный .

Пример

Любой полный двудольный граф $K_{a,b}$ является $(b,a)$-бирегулярный. ромбический додекаэдр Другой пример — ; он (3,4)-бирегулярен.

Количество вершин

Ан $(x,y)$-бирегулярный граф $G=(U,V,E)$ должно удовлетворять уравнению $x|U|=y|V|$. Это следует из простого аргумента двойного подсчета : количество концов ребер в $U$ является $x|U|$, количество концов ребер в $V$ является $y|V|$, и каждое ребро вносит одинаковую сумму (единицу) в оба числа.

Симметрия

Любой регулярный двудольный граф также является бирегулярным.Каждый реберно-транзитивный граф (за исключением графов с изолированными вершинами ), который не является также вершинно-транзитивным, должен быть бирегулярным. В частности, каждый реберно-транзитивный граф является либо регулярным, либо бирегулярным.

Конфигурации

Графы Леви геометрических конфигураций бирегулярны; бирегулярный граф является графом Леви (абстрактной) конфигурации тогда и только тогда, когда его обхват не менее шести.