Шаговый нерегулярный граф — это граф, в котором степени двух смежных вершин отличаются в точности на единицу. Концепцию ввёл в 2018 году как способ изучения графов с минимальной нерегулярностью среди графов с ненулевой разбалансировкой рёбер.
Определение Граф называется шагово нерегулярным, если для любого ребра имеем , где означает степень вершины .
Более обще, граф называется -шагово нерегулярным графом для положительного целого , если для любого ребра . Оригинальные шаговые нерегулярные графы соответствуют случаю .
Базовые свойства Шагово нерегулярные графы имеют несколько фундаментальных структурных свойств. Каждый шагово нерегулярный граф является двудольным. Это следует из факта, что шагово нерегулярные графы не могут содержать нечётных циклов. В любом цикле перемещение вдоль последовательных вершин требует, чтобы степени вершин увеличивались или уменьшались на единицу, что возможно только в случае, если цикл имеет четную длину.
Любой шагово нерегулярный граф имеет чётное число рёбер. Это прямое следствие свойства индекса Альбертсона и факта, что для шагово нерегулярных графов индекс Альбертсона равен числу рёбер.
В шагово нерегулярном графе любое целое между минимальной степенью и максимальной степенью должно появиться в качестве степени некоторой вершины. Граф естественным образом разбивается на две доли — вершины с чётной степенью в одной доле и с нечётной степенью в другой.
Структурные результаты
Ограничения на порядок Возможные порядки (число вершин) шагово нерегулярных графов зависит от их контурнуго ранга :
Деревья (): Порядок всегда нечётен. Шагово нерегулярные графы существуют для всех нечётных порядков, за исключением 1, 5, 8, 13 и 17.
Псевдолеса (): Порядок всегда чётен. Шагово нерегулярные псевдолеса существуют для всех чётных порядков, за исключением 2, 4, 6, 10 и 14
Бициклические графы (): Порядок всегда нечётен. Шагово нерегулярные бициклические графы существуют для всех нечётных порядков, за исключением 1, 3, 7 и 11.
Трициклические графы (): Порядок всегда чётен. Шагово нерегулярные трициклические графы существуют для всех чётных порядков, за исключением 2, 4, 6 и 8.
Связные шагово нерегулярные графы существуют для всех порядков, за исключением 1, 2, 4 и 6.
Диаметр Для -шагово нерегулярных графов доказано, что для любого и любого диаметра существует -шагово нерегулярный граф с диаметром . Такой граф можно получить с помощью произведений графов, таких как прямое и лексикографического произведения графов.
Экстремальные результаты
Для -шагово нерегулярных графов порядка :
Где является максимальной степенью . Равенство выполняется тогда и только тогда, когда изоморфен полному двудольному графу .
Число рёбер в -шагово нерегулярном графе удовлетворяет неравенству
с достижением равенства тогда и только тогда когда степень сложности (то есть граф имеет в точности два разных значения степеней).
Операции над графами Шагово нерегулярные графы не замкнуты относительно общих операций над графами. Удаление любого ребра или вершины из шагово нерегулярного графа к приводит к графу, не являющемуся шагово нерегулярным. Дополнение связного шагово нерегулярного графа никогда не является шагово нерегулярным графом. Подграф разбиения шагово нерегулярного графа, как правило, не является шагово нерегулярным графом, за исключением специальных случаев (, и 3-регулярных графов). Рёберный граф шагово нерегулярного графа не является шагово нерегулярным графом, за исключением случая, когда исходный граф является .
Связь с нерегулярностью графа Шагово нерегулярные графы тесно связаны с индексом Альбертсона, показателем нерегулярности графа определённым как
Эта величина иногда обозначается как и называется в литературе просто нерегулярностью графа. Для шагово нерегулярных графов , что делает их графами с наименьшей нерегулярностью среди графов с ненулевой разбалансировкой рёбер.
Примечания
Категория:Теория графов Категория:Инварианты графов Категория:Алгебраическая теория графов