Полный график

В теории графов переполненный граф — это граф которого , размер больше, чем произведение его максимальной степени и половины его порядка нижнего , т.е. $|E|>\Delta (G)\lfloor |V|/2\rfloor$ где $|E|$ размер G , $\displaystyle \Delta (G)$ - максимальная степень G , а $|V|$ заказ Г. это Сразу следует понятие переполненного подграфа , переполненного графа, который является подграфом . Альтернативное, более строгое определение переполненного подграфа S графа G требует $\displaystyle \Delta (G)=\Delta (S)$ .

Примеры

Каждый нечетный граф циклов длины пять и более переполнен. Произведение его степени (двух) на половину длины (округленное вниз) на единицу меньше количества ребер в цикле. В более общем смысле, каждый регулярный граф с нечетным числом $n$ вершин переполнено, потому что его количество ребер, $\Delta n/2$ (где $\Delta$ — его степень), больше, чем $\Delta \lfloor n/2\rfloor$ .

Характеристики

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

Переполненные графы имеют нечетный порядок.
Переполненные графики относятся к классу 2 . То есть для них требуется не менее $Δ + 1$ цвета в любой раскраске ребер .
Граф G с переполненным подграфом S такой, что $\displaystyle \Delta (G)=\Delta (S)$ , имеет класс 2.

Гипотеза о чрезмерной полноте

В 1986 году Аманда Четвинд и Энтони Хилтон выдвинули следующую гипотезу , которая теперь известна как гипотеза переполнения . ^[1]

Граф G с

\Delta (G)>n/3

является классом 2 тогда и только тогда, когда он имеет переполненный подграф S такой, что

\displaystyle \Delta (G)=\Delta (S)

.

Эта гипотеза, если она верна, будет иметь многочисленные последствия в теории графов, включая гипотезу об 1-факторизации . ^[2]

Алгоритмы

Для графиков, в которых $\Delta \geq n/3$ , существует не более трех индуцированных переполненных подграфов, и найти переполненный подграф можно за полиномиальное время . Когда $\Delta \geq n/2$ , существует не более одного индуцированного переполняющегося подграфа, и его можно найти за линейное время . ^[3]

Ссылки

^ Четвинд, АГ; Хилтон, AJW (1986), «Звездные мультиграфы с тремя вершинами максимальной степени» (PDF) , Mathematical Proceedings of the Cambridge Philosophical Society , 100 (2): 303–317, doi : 10.1017/S030500410006610X , MR 0848854 .
^ Четвинд, АГ; Хилтон, AJW (1989), «1-факторизация регулярных графов высокой степени — улучшенная оценка», Discrete Mathematics , 75 (1–3): 103–112, doi : 10.1016/0012-365X(89)90082-4 , МР 1001390 .
^ Ниссен, Томас (2001), «Как найти переполненные подграфы в графах с большой максимальной степенью. II» , Electronic Journal of Combinatorics , 8 (1), Research Paper 7, MR 1814514 .

[1] Четвинд, АГ; Хилтон, AJW (1986), «Звездные мультиграфы с тремя вершинами максимальной степени» (PDF) , Mathematical Proceedings of the Cambridge Philosophical Society , 100 (2): 303–317, doi : 10.1017/S030500410006610X , MR 0848854 .

[2] Четвинд, АГ; Хилтон, AJW (1989), «1-факторизация регулярных графов высокой степени — улучшенная оценка», Discrete Mathematics , 75 (1–3): 103–112, doi : 10.1016/0012-365X(89)90082-4 , МР 1001390 .

[3] Ниссен, Томас (2001), «Как найти переполненные подграфы в графах с большой максимальной степенью. II» , Electronic Journal of Combinatorics , 8 (1), Research Paper 7, MR 1814514 .

[1]

[2]

[3]