Переполненный граф

Переполненный граф (Шаблон:Lang-en) Шаблон:Sfn — это такой простой граф $G$ (без кратных ребер и петель), размер которого $|E|$ больше произведения максимальной степени его вершин $\mathrm{\Delta }(G)$ на округлённую вниз половину его порядка $|V|$

$|E|>\mathrm{\Delta }(G)\lfloor |V|/2\rfloor$.

Если граф $G$ имеет переполненный подграф $S$ и $\mathrm{\Delta }(S)$ = $\mathrm{\Delta }(G)$ то $G$ - называется графом с переполненным подграфом (Шаблон:Lang-en)Шаблон:SfnШаблон:Sfn.

Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$, и тогда граф принадлежит к Классу 1, либо ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)+1$ и тогда граф принадлежит к Классу 2.

Свойства

Некоторые свойства переполненных графов:

• Из теоремыШаблон:Sfn, которая гласит, что если граф $G$ обладает размером $|E|$, таким что $|E|>{\beta }_1(G)\mathrm{\Delta }(G)$, где ${\beta }_1(G)$ есть реберное число независимости, а $\mathrm{\Delta }(G)$ есть максимальная степень его вершин , то граф $G$ принадлежит Классу 2, и условия, что если граф порядка $|V|$, то его реберное число независимости ${\beta }_1(G)=\lfloor |V|/2\rfloor$, вытекает свойство:

Переполненный граф является графом Класса 2

• Доказывается как теоремаШаблон:Sfn:

Если у графа есть переполненный подграф, то сам граф - переполненный

• Доказывается как теоремаШаблон:Sfn.

Порядок переполненного графа - нечётное число

Гипотеза о переполнении

Четуинд и Хилтон Шаблон:Sfn в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении (Шаблон:Lang-en)

Если для максимальной степени вершин графа выполняется условие $3\mathrm{\Delta }(G)⩾|V|$, где $|V|$ есть порядок графа, то граф $G$ принадлежит к Классу 2 тогда и только тогда, когда он является графом с переполненным подграфом.

Эта гипотеза, если верна, имела бы многочисленные приложения к теории графов, включая гипотезу об 1-факторизации Шаблон:Sfn.

Алгоритмы

В работеШаблон:Sfn приводится алгоритм, которые позволяет найти для графа $G$ у которого $|V(S)|>|V(G)|-\mathrm{\Delta }(G)$ все порожденные переполненные подграфы $S$ за время $O(n\log (n)+m)$, где $n=|V(G)|$ и $m=|E(G)|$.

Вариант этого алгоритма позволяет для графа $G$, у которого $2\mathrm{\Delta }(G)\ge |V(G)|$ найти все порожденные переполненные подграфы за линейное время $O(n+m)$.

Также в работе приводится второй алгоритм, работающий с использованием первого алгоритма, который позволяет найти все порожденные переполненные подграфы графа $G$, у которого $3\mathrm{\Delta }(G)\ge |V(G)|$ в общем случае за полиномиальное время $O(n^{5/3}m)$, а для регулярного графа $G$ за время $O(n^3)$.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья (Research Paper 7)