Переполненный граф () — это такой простой граф (без кратных ребер и петель), размер которого больше произведения максимальной степени его вершин на округлённую вниз половину его порядка
.
Если граф имеет переполненный подграф и = то - называется графом с переполненным подграфом ().
Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо , и тогда граф принадлежит к Классу 1, либо и тогда граф принадлежит к Классу 2.
Свойства
Некоторые свойства переполненных графов:
Из теоремы, которая гласит, что если граф обладает размером , таким что , где есть реберное число независимости, а есть максимальная степень его вершин , то граф принадлежит Классу 2, и условия, что если граф порядка , то его реберное число независимости , вытекает свойство:
Переполненный граф является графом Класса 2
Доказывается как теорема:
Если у графа есть переполненный подграф, то сам граф - переполненный
Доказывается как теорема.
Порядок переполненного графа - нечётное число
Гипотеза о переполнении Четуинд и Хилтон в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении ()
Если для максимальной степени вершин графа выполняется условие , где есть порядок графа, то граф принадлежит к Классу 2 тогда и только тогда, когда он является графом с переполненным подграфом.
Эта гипотеза, если верна, имела бы многочисленные приложения к теории графов, включая гипотезу об 1-факторизации .
Алгоритмы В работе приводится алгоритм, которые позволяет найти для графа у которого все порожденные переполненные подграфы за время , где и .
Вариант этого алгоритма позволяет для графа , у которого найти все порожденные переполненные подграфы за линейное время .
Также в работе приводится второй алгоритм, работающий с использованием первого алгоритма, который позволяет найти все порожденные переполненные подграфы графа , у которого в общем случае за полиномиальное время , а для регулярного графа за время .
Примечания
Литература
(Research Paper 7)
Категория:Семейства графов