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

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

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

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

Пример

Каждый полный двудольный граф ${\displaystyle K_{a,b}}$ является ${\displaystyle (b,a)}$-бирегулярный.^[3]В ромбический додекаэдр еще один пример; оно (3,4) -бирегулярно.^[4]

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

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

Симметрия

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

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

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

Рекомендации

1. Шайнерман, Эдвард Р.; Ульман, Дэниел Х. (1997), Теория дробных графов, Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., стр. 137, ISBN  0-471-17864-0, МИСТЕР  1481157.
2. Демер, Матиас; Эммерт-Штрейб, Франк (2009), Анализ сложных сетей: от биологии до лингвистики, John Wiley & Sons, стр. 149, ISBN  9783527627998.
3. Лаури, Йозеф; Скапеллато, Рафаэле (2003), Темы автоморфизмов и реконструкции графов, Тексты студентов Лондонского математического общества, Cambridge University Press, стр. 20–21, ISBN  9780521529037.
4. Рети, Тамаш (2012), «О соотношении между первым и вторым индексами Загреба» (PDF), MATCH Commun. Математика. Comput. Chem., 68: 169–188, архивировано с оригинал (PDF) на 2017-08-29, получено 2012-09-02.
5. Гропп, Харальд (2007), «Конфигурации VI.7», в Colbourn, Charles J .; Диниц, Джеффри Х. (ред.), Справочник комбинаторных планов, Дискретная математика и ее приложения (Бока-Ратон) (второе изд.), Chapman & Hall / CRC, Бока-Ратон, Флорида, стр. 353–355..