Степенное множество графа

Степенным множеством графа называется множество степеней его вершин. От степенной последовательности о множество отличается тем, что в нем не учитывается число вершин, имеющих заданную степень, тогда как в степенной последовательности каждое число фигурирует столько раз, степенью скольких вер­шин оно является.

Степенное множество графа G обоз­начим через S(G). Так, для графа G, изображенного на рис. 52.1, S(G) = = {1, 2, 3}.

Хотя степенная последовательность графа удовлетворяет определенным условиям, однако степенным множеством графа может быть произвольное множество. Об этом свидетельствует следующая

Теорема 52.1. Любое конечное множество S натуральных чисел является степенным множеством некоторого порогового графа. Минимальный порядок таких графов равен s +1, где s — максимальное число из множества S. Очевидно, что из этой теоремы вытекает

Следствие 52.2. Любое конечное множество целых, неотрицательных чисел является степенным множеством некоторого графа.

Доказательство теоремы 52.1. Если S(G) = = S, то \G\ ≥ s+ 1, так что нужно только доказать су­ществование подходящего графа G. Утверждение триви­ально для одноэлементного множества S, поскольку S(K_n)={n — 1}. Пусть теперь

и пусть, для определенности, п = 2р — четное число. Нуж­ный граф будем искать в виде

где К_Х°Н- граф, полученный из графа Н добавлением х доминирующих вершин, а О_У°Н — граф, полученный из графа Н добавлением у изолированных вершин. Лю­бой граф вида (1) является пороговым. Попытаемся по­добрать числа х_а и y_β в выражении (1) так, чтобы вы­полнялось - равенство S(G) = S. Для этого должно быть

Очевидно, что систем а ур авнений (2) относительно не­известных х_i, yj (i =1,p,j =1, р) имеет решение, все координаты которого положительны:

Подставив в выражение (1) числа, определяемые равенст­вами (3), получим граф G, для которого S(G)=S. Число его вершин равно

Для нечетного п = 2р + 1 построение аналогично, толь-to вместо формулы (1) используется формула

Глава IX