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