Гипотеза о разбалансировке — это открытая проблема теории графов, ставящая вопрос, являются ли последовательности разбалансировки рёбер гафическими. Гипотезу высказали Козеренко и Скочко в 2014 году.
Определения
Для простого неориентированного графа разбалансировка ребра определяется как::
где и обозначает степени вершин и .
Последовательность разбалансировки — это мультимножество всех разбалансировок рёбер графа .
Последовательность неотрицательных целых называется графической, если этопоследовательностью степеней некоторого графа. Граф называется графически разбалансированным, если его последовательность разбалансировки является графической.
Утверждение гипотезы
Гипотеза о разбалансировке: Если для всех рёбер имеем , то графическая.
Другими словами, если нет в графе рёбер соединяющих вершины с одинаковой степенью, то мультимножество разбалансировки рёбер формирует допустимую последовательность для некоторого графа.
Предыстория
Концепцию разбалансировки рёбер предложил в 1997 году Альбертсон как показатель нерегулярности графа. Нерегулярность графа определяется как
Иногда эта величина называется индексом Альбертсона и обозначается в литературе как . Хотя значительное количество исследований было посвящено границам для нерегулярности графов, Козеренко и Скочко первыми систематически изучили последовательности разбалансированности как самостоятельные объекты исследования.
Известные результаты
Гипотеза о разбалансировке была вычислительно проверена для всех графов с не более чем 9 вершинами, удовлетворяющих условию, что рёбра имеют положительную разбалансировку. Позднее этот результат был улучшен до 12 вершин.
Для некоторых классов графов было доказано наличие графических последовательностей разбалансировки. Козеренко и Скочко доказали, что следующие классы графов графически разбалансированы: Все деревья Графы, в которых все вершины, не являющиеся листьями, образуют клику Полные расширения путей Полные расширения циклов Полные расширения полных графов Графы с постоянной разбалансировкой рёбер
Козеренко и Сердюк обнаружили дополнительно классы графически разбалансированных графов: Все псевдолеса (графы с одним циклом) Антирегулярные графы (графы с единственной парой вершин, имеющих одинаковые степени) Соединения графов с достаточно большими пустыми графами Двойные графы графически разбалансированных графов Три специальных классов блоковых графов: Блоковые графы, в которых все разрезающие вершины Разрезающая вершина — это вершина, удаление которой увеличивает число связных компонент графа принадлежат одному блоку Блоковые графы, в которых разрезающие вершины порождают звёзды Блоковые графы, в которых разрезающие вершины порождают пути
Было показано, что некоторые операции над графами сохраняют свойство быть графически разбалансированными:
Если и графически разбалансированны, то их также графически разбалансированно Если графически разбалансированны, то (соединение с одной вершиной) также графически разбалансированно Двойной граф графически разбалансированного графа также графически разбалансирован
Связанные гипотезы
Одно связанное предположение касается «среднего дисбаланса» непустого графа G, определяемого как
Гипотеза о средней разбалансировке: Если , то iявляется графической.
Эту гипотезу опровергли Козеренко и Сердюк в 2023 году, показав, что для любого вещественного числа существует разбалансированный граф , не являющийся графическим, с .
Гипотеза о бициклических графах: Существует в точности один связный бициклический разбалансированный неграфический граф (показано существование среди графов с числом вершин не более 21).
Гипотеза о блоковых графах: Все блоковые графы графически разбалансированны.
Эта гипотеза проверена для всех блоковых графов с числом вершин не более 13. Слабая версия этой гипотезы предполагает, что все линейные графы деревьев (которые являются в точности блочными графами без клешней) являются графически разбалансированными.
Смотрите также Последовательность степеней вершин Теорема Эрдёша — Галлаи
Примечания
Категория:Теория графов Категория:Математические гипотезы Категория:Нерешённые проблемы теории графов